3075: 下降幂多项式

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:26 解决:23

题目描述

x 的 k 次下降幂定义为

x(k)=(x)(x−1)(x−2)⋯(x−k+1)

x 的下降幂多项式是由 x 的一组下降幂及系数组成的算式:

f(x)=anx(n)+an−1x(n−1)+⋯+a2x(2)+a1x(1)+a0

给定下降幂多项式 f(x) 的系数an,an−1,⋯,a0 与一个值 m,请计算 f(m)mod 1,000,000,007。


输入

  • 第一行:两个整数 n 与 m
  • 第二行:n+1 个整数 an,an−1,⋯,a1,a0
  • 30% 的数据,1≤n≤10
  • 60% 的数据,1≤n≤5,000
  • 100% 的数据,1≤n≤300,000
  • −10^9≤m≤10^9
  • −10^9≤ai≤10^9

输出

  • 单个整数:表示 f(m)mod1,000,000,007。

样例输入 复制

3 5
4 3 2 1

样例输出 复制

311

提示

f(x) = 4(x)(x-1)(x-2)+3(x)(x-1)+2(x)+1
f(5) = 4(5)(4)(3)+3(5)(4)+2(5)+1=240+60+10+1