Inaho is given a function:

$${\displaystyle f(x)=\{\begin{array}{ll}{a}_{1}f(x-1)+a_{2}f(x-2)+\cdots +a_{N}f(x-N)& \text{if }x>N\\ 1& \text{if }x\le N\end{array}}$$

Given $N,Z$ and $a$, Inaho wants you to print $f(Z)mod{10}^9+7$.

Input Specification

The first line will contain two integers, $N,Z$ $(1\le N\le 10,1\le Z<{10}^{10000})$.

The second line will contain $N$ integers, $a_1,a_2,\dots ,a_N$ $(1\le a_i\le {10}^6)$.

Output Specification

Print $f(Z)mod{10}^9+7$.

Subtasks

Subtask 1 [10%]

$Z<{10}^5$

Subtask 2 [30%]

$Z<{10}^{18}$

Subtask 3 [60%]

No additional constraints.

Sample Input 1

2 5
1 1

Sample Output 1

5

Sample Input 2

6 90000
4 2 29 5 1 10

Sample Output 2

408918679