← 返回题目列表

AtCoder · arc033_4

D. 你以前从未见过的多项式

中文机器翻译题面 查看原题

問題文

高桥君没见过 他说他发现了 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