問題文
高桥君没见过 他说他发现了 N 次多項式 P(x) 。该多项式的系数均为正整数。高桥君给你 它给了我 P(0) 〜 P(N) 的值。现在你在这里 你能猜出 P(T) 的值吗?
入力
输入是按以下格式从标准输入给出的。
N A_0 A_1 ... A_N T
- 1 行包含一个整数,表示 Takahashi 找到的多项式的次数。 在 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