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
f(5) = 4(5)(4)(3)+3(5)(4)+2(5)+1=240+60+10+1