题目描述

高桥君有一个未知的$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$