AT_arc033_4 [ARC033D] 見たことのない多項式

[problemUrl]: https://atcoder.jp/contests/arc033/tasks/arc033_4 高橋君は、見たことのない $ 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) $ であることを表す。

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

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 100 $ を満たすテストケース全てに正解した場合は、$ 40 $ 点が与えられる。 - $ N\ ≦\ 3,000 $ を満たすテストケース全てに正解した場合は、$ 80 $ 点が与えられる。 ### Sample Explanation 1 このケースでは、$ 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 $ となります。