고대 마법사가 남긴 비전서에는 신비로운 수열이 기록되어 있다. 이 수열은 첫 세 항 \(f(0)=a,\ f(1)=b,\ f(2)=c\)와 점화식

$$ f(n) = p \cdot f(n-1) + q \cdot f(n-2) + r \cdot f(n-3) \quad (n \ge 3) $$

으로 정의된다. 모든 계산은 소수 \(M\)으로 나눈 나머지를 사용한다.

정수 \(n\)이 주어질 때, \(f(n) \bmod M\)을 구하여라.

• \(0 \le a, b, c < M\)
• \(0 \le p, q, r < M\)
• \(0 \le n \le 10^{17}\)
• \(2 \le M \le 10^9+7\), \(M\)은 소수이다.

첫째 줄에 세 정수 \(a,\ b,\ c\)가 공백으로 구분되어 주어진다.

둘째 줄에 세 정수 \(p,\ q,\ r\)이 공백으로 구분되어 주어진다.

셋째 줄에 정수 \(n\)과 소수 \(M\)이 공백으로 구분되어 주어진다.

\(f(n) \bmod M\)을 출력한다.

riseoj 작성

출처 Original