问题文

高桥君似乎发现了一个他从未见过的 $N$ 次多项式 $P(x)$。据说这个多项式的系数都是正整数。高桥君告诉了你 $P(0)$ 到 $P(N)$ 的值。现在，你能猜出 $P(T)$ 的值吗？

输入

输入以以下格式从标准输入中给出：

$N$ $A_0$ $A_1$ ... $A_N$ $T$

• 第一行包含一个整数 $N (1 \leq N \leq 10^5)$，表示高桥君发现的多项式的次数。
• 第二行包含 $N+1$ 个整数，以空格分隔。其中第 $i-1$ 个整数 $A_{i-1} (0 \leq A_{i-1} \leq 10^9+6)$ 表示将 $P(i-1)$ 的值除以 $1,000,000,007 (10^9+7)$ 所得到的余数。
• 第三行包含一个整数 $T (1 \leq T \leq 10^9)$，表示你需要猜测的 $P(T)$ 的值。

部分点

此问题设有部分点。

• 如果对于所有满足 $N \leq 100$ 的测试用例都能够正确回答，则得到 40 分。
• 如果对于所有满足 $N \leq 3,000$ 的测试用例都能够正确回答，则得到 80 分。

输出

请在一行中输出 $P(T)$ 的值除以 $1,000,000,007 (10^9+7)$ 所得到的余数。这样的值是唯一确定的。请在末尾添加换行符。

输入示例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