背景

备选

描述

现在有一个一元n次方程f(x) = a[1] * x^n + a[2] * x ^(n - 1)... + a[n] * x + a[n + 1]

但是我们并不知道a[1]~a[n + 1]的具体数值,我们只知道f(0)~f(n)的值。

现在询问的值是多少。

注意,输入的f是对10^9+7取模后的结果

当然,答案可能很大,最后对10^9+7取模即可。

输入格式

第一行一个数n,意义如题

第二行n+1个正整数,表示f(0)~f(n)

第三行一个数s,意义如题

输出格式

一个数,表示答案

样例输入

1

1 2

2

样例输出

6

数据范围与约定

1<=n<=1000, 1<=s<=10^9

 

样例解释