上海计算机学会将在第X届（时间）比赛中进行C++丙组T2题目的降幂排列计算

题目描述

x 的 k 次降幂被定义为

由 x 的一系列下降幂及其对应的系数构成的表达式，即为 x 的下降幂多项式。

已知下降幂多项式 f(x) 的各项系数分别为 an、an−1、…、a0，以及一个数值 m，请计算 f(m) 对 1,000,000,007 取模的结果。

输入格式

• 首行输入：两个整数 n 和 m
  • 次行输入：an, an−1, ⋯, a1, a0

输出格式

• 单个整数：用于表示 f(m) 除以 1,000,000,007 后的余数。

数据范围

• 30% 的数据，1≤n≤10
  • 60% 的数据，1≤n≤5,000
  • 100% 的数据，1≤n≤300,000
  • −109≤m≤109
  • −109≤ai≤109

样例数据展示

3 5

4 3 2 1

输出:

311