Problem Description

Takahashi claims to have found a polynomial $ P(x) $ of degree $ N $ that he has never seen before. All the coefficients of this polynomial are positive integers. Takahashi has told you the values of $ P(0) $ through $ P(N) $. Now, can you determine the value of $ P(T) $?

Input Format

The input is given from the standard input in the following format:

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

• The first line contains an integer $N\ (1\ ≦\ N\ ≦\ 10^5)$, representing the degree of the polynomial found by Takahashi.
• The second line contains $ N+1 $ integers separated by spaces. The $ i $-th integer $A_{i-1}\ (0\ ≦\ A_{i-1}\ ≦\ 10^9+6)$ represents the value of $ P(i-1) $ modulo $1,000,000,007\ (10^9+7)$.
• The third line contains an integer $T\ (1\ ≦\ T\ ≦\ 10^9)$, indicating that you need to determine the value of $ P(T) $.

Output Format

Output the value of $ P(T) $ modulo $1,000,000,007\ (10^9+7)$ in one line. It is guaranteed that such a value is uniquely determined. End the output with a newline.

Sample Input and Output

Sample Input #1

2
1 3 7
3

Sample Output #1

13

Sample Input #2

5
4 16 106 484 1624 4384
1000000000

Sample Output #2

999984471

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $N\ ≦\ 100$, you will be awarded $ 40 $ points.
• If you correctly solve all test cases where $N\ ≦\ 3,000$, you will be awarded $ 80 $ points.

Sample Explanation 1

In this case, $ P(0)=1, P(1)=3, P(2)=7 $, and the polynomial $ x^2+x+1 $ satisfies the conditions. In this case, $ P(3)=13 $, so you should output $ 13 $. There are other polynomials that satisfy the conditions, such as $ x^2+x+10^9+8 $, but the remainder of $ P(3) $ modulo $ 10^9+7 $ is always $ 13 $.

见题面 Input 部分

见题面 Output 部分