AT_arc033_4 [ARC033D] 見たことのない多項式
题目描述
高桥君有一个未知的 $N$ 次多项式 $P(x)$，只知道 $P(x)$在$x=0,1,2,3\cdots N$ 时的值。高桥君希望知道当 $x=T$ 时，多项式的值。结果对 $10^9+7$ 取模。
输入格式
输入数据共三行。
第一行一个 $N$ 表示多项式次数。
第二行 $N+1$ 个数顺次表示 $P(x)$ 在 $0\sim N$ 处的值 $A_i$。
第三行一个数 $T$，表示询问。
输出格式
共一行一个数，表示 $P(T)$ 在 $\bmod\ 10^9+7$ 意义下的答案。
说明/提示
对于 $40 \%$ 的数据，满足 $N \leq 100$。
对于 $80 \%$ 的数据，满足 $N \leq 3000$。
对于全部 $100 \%$ 的数据，$1 \leq N \leq 10^5$, $0 \leq A_i \leq 10^9+6$, $T \leq 10^9$。