George the Ghost returns home with bags full of candy. He lays them out on the table, opens his mouth, and... you didn't think he was gonna eat them, did you?

Of course not! Firstly, George is a ghost, and he cannot eat solid food. Secondly, George is a magic ghost - he was going to cast spells to duplicate his candy!

George has ~N~ ~(1 \le N \le 10^6)~ types of candy laid out in a row. Initially (at time ~0~), he has ~a_i~ (~1 \le a_i \le 10^9~) of the ~i~-th type of candy. Then, each second, he performs the following operation:

Set ~a_i~ to ~b_i~ for all ~1 \le i \le N~ at once, where

$$\displaystyle b_i = \sum_{k=1}^{i} a_k $$

After ~T~ (~1 \le T \le 10^6~) seconds, how much total candy he will have? This might be a big number, so print it modulo ~10^9 + 7~.

I'm not familiar with modulo ~10^9 + 7~

When solving problems that ask for an answer ~mod~ a large prime number, this often means that you have to use 64-bit numbers, such as long in Java or long long in C++.

When performing addition and multiplication operations, ~mod~, often denoted by ~\%~, is distributive:

~(a \times b) \% m = ((a \% m) \times (b \% m)) \% m~, and
~(a + b) \% m = ((a \% m) + (b \% m)) \% m~

When performing subtraction, you might need to do it as follows to avoid performing a negative number ~\% m~ (i.e. in case ~a - b~ is negative):

~(a - b + m) \% m~

Finally, for division... things get complicated. Read the following articles below to better understand it.
CP-Algorithms - Modular Inverse using Binary Exponentiation
Geeks4Geeks - Modular Division

Input Specifications

On the first line, an integer ~N~ (~1 \le N \le 10^6~), the number of types of candy.

On the second line, ~N~ space-separated integers: ~a_i~ (~1 \le i \le N~), the starting number of each type of candy.

On the third and last line, an integer ~T~ (~1 \le T \le 10^6~), the number of seconds that pass.

Output Specifications

Print one integer: the total number of candy George will have after ~T~ seconds, modulo ~10^9 + 7~.

Note for Python users: To pass this question, you must select the PyPy interpreter instead of the normal one.

Constraints

Subtask 1 [20%]:

~1 \le N \le 10^3~

~1 \le T \le 10^3~

Subtask 2 [80%]:

No further constraints.

Sample Input 1

4
3 2 2 1
3

Sample Output 1

89

Sample Output 1 Explanation

After ~1~ second, the number of candies of each type is:

3 5 7 8

After ~2~ seconds:

3 8 15 23

After ~3~ seconds:

3 11 26 49

~3 + 11 + 26 + 49 = 89~, so he has 89 pieces of candy.