AtCoder Regular Contest 033

D - 見たことのない多項式


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は、見たことのない 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

Submit提出する