Problem Statement

高橋君は、見たことのない $N$ 次多項式 $P(x)$ を見つけたそうです。この多項式の係数は全て正整数だそうです。高橋君はあなたに $P(0)$ 〜 $P(N)$ の値を教えてくれました。さてここで、あなたは $P(T)$ の値を当てることができるでしょうか。

Input

入力は以下の形式で標準入力から与えられる。

N
A_0 A_1 ... A_N
T

• $1$ 行目には、高橋君が見つけた多項式の次数を表す整数 $N (1 ≦ N ≦ 10^5)$ が与えられる。
• $2$ 行目には、$N+1$ 個の整数が空白区切りで与えられる。このうち $i$ 番目の整数 $A_{i-1} (0 ≦ A_{i-1} ≦ 10^9+6)$ は、$P(i-1)$ の値を $1,000,000,007 (10^9+7)$ で割った余りを表す。
• $3$ 行目には、整数 $T (1 ≦ T ≦ 10^9)$ が与えられる。これは、あなたが当てなければならない値が $P(T)$ であることを表す。

部分点

この問題には部分点が設定されている。

• $N ≦ 100$ を満たすテストケース全てに正解した場合は、$40$ 点が与えられる。
• $N ≦ 3,000$ を満たすテストケース全てに正解した場合は、$80$ 点が与えられる。

Output

$P(T)$ の値を $1,000,000,007 (10^9+7)$ で割った余りを $1$ 行に出力せよ。このような値は一意に定まることが保証される。出力の末尾に改行を入れること。