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$。