차수 \(K\)인 선형 점화식이 있다. 수열 \(a\)는 다음을 만족한다.

$$ a_m = c_1 a_{m-1} + c_2 a_{m-2} + \cdots + c_K a_{m-K} \quad (m \ge K) $$

초기항 \(a_0, a_1, \dots, a_{K-1}\)과 계수 \(c_1, \dots, c_K\)가 주어진다. 정수 \(N\)에 대해 \(a_N\)을 \(1{,}000{,}000{,}007\)로 나눈 나머지를 구하여라.

\(N\)이 최대 \(10^{18}\)까지 매우 클 수 있으므로 항을 하나씩 계산할 수 없다.

\(1 \le K \le 500\)

\(0 \le N \le 10^{18}\)

\(0 \le a_i, c_i < 1{,}000{,}000{,}007\)

첫 줄에 점화식의 차수 \(K\)와 항 번호 \(N\)이 주어진다.

둘째 줄에 초기항 \(a_0, a_1, \dots, a_{K-1}\)이 주어진다.

셋째 줄에 계수 \(c_1, c_2, \dots, c_K\)가 주어진다. 모든 입력값은 음이 아닌 정수이며 이미 \(1{,}000{,}000{,}007\) 미만이다.

\(a_N \bmod 1{,}000{,}000{,}007\)을 한 줄에 출력한다.

riseoj 작성

출처 Original