問題文

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

入力

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

$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$ 点が与えられる。

出力

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

入力例1

2
1 3 7
3

出力例1

13

このケースでは、$P(0)=1,P(1)=3,P(2)=7$ であり、$x^2+x+1$ という多項式が条件を満たします。このとき $P(3)=13$ であるため $13$ を出力します。他にも $x^2+x+10^9+8$ などの多項式が条件を満たしますが、$P(3)$ を $10^9+7$ で割った余りはいずれも $13$ となります。

入力例2

5
4 16 106 484 1624 4384
1000000000

出力例2

999984471