Product Oriented Recurrence

시간 제한1초메모리 제한1024 MB

요약

c의 거듭제곱 인수가 곱해지는 곱셈 점화식의 n번째 항을 10억 7로 나눈 나머지로 구한다. n은 10^18까지다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 행렬, 조합론
정답자: 아직 제출이 없습니다

문제

Let $f\_{x} = c^{2x-6} \cdot f\_{x-1} \cdot f\_{x-2} \cdot f\_{x-3}$ for $x \ge 4$ .

You have given integers $n$ , $f\_{1}$ , $f\_{2}$ , $f\_{3}$ , and $c$ . Find $f\_{n} \bmod (10^{9}+7)$ .

입력

The only line contains five integers $n$ , $f\_{1}$ , $f\_{2}$ , $f\_{3}$ , and $c$ ( $4 \le n \le 10^{18}$ , $1 \le f\_{1}$ , $f\_{2}$ , $f\_{3}$ , $c \le 10^{9}$ ).

출력

Print $f\_{n} \bmod (10^{9} + 7)$ .

힌트

In the first example, $f\_{4} = 90$ , $f\_{5} = 72900$ .

In the second example, $f\_{17} \approx 2.28 \times 10^{29587}$ .

예제2

예제 1
입력
```
5 1 2 5 3
```
예상 출력
```
72900
```
예제 2
입력
```
17 97 41 37 11
```
예상 출력
```
317451037
```