차수 \(k\)의 수열은 \(n \ge k\)에 대해 \(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}\)로 정의되며, 초기항 \(a_0, \dots, a_{k-1}\)이 주어진다. 계수, 초기항, 인덱스 \(n\)이 주어질 때 \(a_n \bmod (10^9+7)\)을 출력하시오. 큰 \(n\)을 위해 행렬 거듭제곱을 사용한다.

첫 줄에 \(k\) (\(1 \le k \le 6\))가 주어진다. 둘째 줄에 \(k\)개의 계수 \(c_1, \dots, c_k\)가 주어진다 (\(0 \le c_i \le 100\)). 셋째 줄에 \(k\)개의 초기항 \(a_0, \dots, a_{k-1}\)이 주어진다 (\(0 \le a_i \le 10^9\)). 넷째 줄에 \(n\)이 주어진다 (\(0 \le n \le 10^{18}\)).

\(a_n \bmod (10^9+7)\)을 출력한다.

riseoj 작성

출처 RiseOJ Basics