The N-th Term of a Recurrence

Difficulty: 1900 4000 ms 128 MB

dp matrix-exponentiation

A sequence obeys f(i) = c₁f(i−1) + c₂f(i−2) + … + c_Kf(i−K) with given constant coefficients and the first K values. Print f(N) modulo 10⁹+7.

Input: the first line has K and N; the second line has c₁..c_K; the third line has f(0)..f(K−1).

Output: f(N) mod 10⁹+7.

Constraints:

• 1 ≤ K ≤ 6
• 0 ≤ N ≤ 10¹⁸
• 0 ≤ c_i, f(i) ≤ 10⁹

Sample Tests

2 10
1 1
0 1

55

1 5
2
3

96

Read the Editorial