提交翻译

**题目描述**

高桥君有一个未知的$n$次多项式$P(x)$，只知道$P(x)$在$x=0,1,2,3\cdots n$时的值。高桥君希望知道当$x=T$时，多项式的值。结果对$10^9+7$取模。

**输入格式**

输入数据共三行。

第一行一个$N$表示多项式次数。

第二行$N+1$个数顺次表示$P(x)$在$0$~$N$处的值$A_i$。

第三行一个数$T$，表示询问。

**输出格式**

共一行一个数，表示$P(T)$在$ \mod{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$