별빛이 일렬로 늘어선 \(1 \times N\) 크기의 띠를 별 타일로 빈틈없이, 겹치지 않게 덮으려고 한다. 사용할 수 있는 타일은 길이가 각각 \(1\), \(2\), \(3\) 인 세 종류이며, 별 무늬가 서로 달라서

• 길이 \(1\) 짜리 타일은 서로 다른 무늬가 \(A\) 가지,
• 길이 \(2\) 짜리 타일은 서로 다른 무늬가 \(B\) 가지,
• 길이 \(3\) 짜리 타일은 서로 다른 무늬가 \(C\) 가지

존재한다. 어떤 한 칸을 덮는 타일의 길이가 다르거나, 길이가 같더라도 그 타일의 무늬가 다르면 서로 다른 타일링으로 센다.

예를 들어 \(A = B = C = 1\) (각 길이마다 무늬가 한 가지뿐) 이고 \(N = 4\) 이면 타일 길이 배열 기준으로 \(1{+}1{+}1{+}1,\; 1{+}1{+}2,\; 1{+}2{+}1,\; 2{+}1{+}1,\; 2{+}2,\; 1{+}3,\; 3{+}1\) 의 \(7\) 가지가 있다.

\(1 \times N\) 띠를 덮는 서로 다른 타일링의 수를 소수 \(P\) 로 나눈 나머지를 출력하여라. \(N\) 이 매우 클 수 있음에 유의하라.

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

\(1 \le A \le 10^{9}\), \(0 \le B \le 10^{9}\), \(0 \le C \le 10^{9}\)

\(P\) 는 \(2 \le P \le 2 \times 10^{9}\) 인 소수

한 줄에 다섯 개의 정수 \(N\), \(A\), \(B\), \(C\), \(P\) 가 공백으로 구분되어 주어진다.

\(0 \le N \le 10^{18}\) 이고, \(0 \le A, B, C \le 10^{9}\) 이며 \(A \ge 1\) 이 보장된다. \(P\) 는 \(2 \le P \le 2 \times 10^{9}\) 인 소수이다.

\(1 \times N\) 띠를 덮는 서로 다른 타일링의 수를 \(P\) 로 나눈 나머지를 한 줄에 출력한다. (길이 \(0\) 인 띠를 덮는 방법은 \(1\) 가지로 본다.)

riseoj 작성

출처 Original