Let

$$\displaystyle f(x) = \begin{cases} a_1f(x-1) + a_2f(x-2) + \ldots + a_Nf(x-N) & \text{if } x > N \\ 1 & \text{if } x \le N \end{cases} $$

Given ~N, Z~ and ~a~, print ~f(Z) \bmod 10^9 + 7~.

Input Specification

The first line will contain two integers, ~N, Z~ ~(1 \le N \le 10, 1 \le Z \le 10^5)~.

The second line will contain ~N~ integers, ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10^6)~.

Output Specification

Print ~f(Z) \bmod 10^9+7~.

Subtasks

Subtask 1 [20%]

~N = 2, a_i = 1, Z \le 20~

Subtask 2 [30%]

~N = 2, a_i = 1~

Subtask 3 [50%]

No further constraints.

Sample Input 1

2 5
1 1

Sample Output 1

5

Sample Input 2 (not in pretests)

6 90000
4 2 29 5 1 10

Sample Output 2

408918679