Bảng Giá Trị Liên Tiếp

Mọi phép tính được thực hiện theo modulo $1000000007$.

Cho một đa thức $P$ có bậc không quá $N$. Bạn biết lần lượt các giá trị $P(0),P(1),\dots ,P(N)$. Hãy tính $P(T)$.

Input

• Dòng đầu chứa số nguyên $N$.

• Dòng thứ hai chứa $N+1$ số nguyên $A_0,A_1,\dots ,A_N$, trong đó $A_i=P(i)\mathrm{mod}1000000007$.

• Dòng thứ ba chứa số nguyên $T$.

Output

• In $P(T)\mathrm{mod}1000000007$ dưới dạng số dư trong $[0,10^9+6]$.

Constraints

• $1\le N\le 10^5$.
• $0\le A_i<1000000007$.
• $1\le T\le 10^9$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 30$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2
1 4 9
3

16

3
0 1 8 27
5

125