Inaho IX

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

Inaho is given a function:

\[ 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\), Inaho wants you to 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 < 10^{10\ 000})\).

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 [10%]

\(Z < 10^5\)

Subtask 2 [30%]

\(Z < 10^{18}\)

Subtask 3 [60%]

No further 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

Comments

There are no comments at the moment.