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

**题目描述** 高桥君有一个未知的 $N$ 次多项式 $P(x)$，只知道 $P(x)$在$x=0,1,2,3\cdots N$ 时的值。高桥君希望知道当 $x=T$ 时，多项式的值。结果对 $10^9+7$ 取模。 **输入格式** 输入数据共三行。 第一行一个 $N$ 表示多项式次数。 第二行 $N+1$ 个数顺次表示 $P(x)$ 在 $0\sim N$ 处的值 $A_i$。 第三行一个数 $T$，表示询问。 **输出格式** 共一行一个数，表示 $P(T)$ 在 $\bmod\ 10^9+7$ 意义下的答案。 **提示** 对于 $40 \%$ 的数据，满足 $N \leq 100$。 对于 $80 \%$ 的数据，满足 $N \leq 3000$。 对于全部 $100 \%$ 的数据，$1 \leq N \leq 10^5$, $0 \leq A_i \leq 10^9+6$, $T \leq 10^9$。

[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 $ 行に出力せよ。このような値は一意に定まることが保証される。出力の末尾に改行を入れること。

2
1 3 7
3

13

5
4 16 106 484 1624 4384
1000000000

999984471

### 部分点 この問題には部分点が設定されている。 - $ 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 $ となります。