곱으로 정의된 점화식

다음과 같이 정의된 수열 $f\_{x}$가 있다. $x \ge 4$일 때 $f\_{x} = c^{2x-6} \cdot f\_{x-1} \cdot f\_{x-2} \cdot f\_{x-3}$이다.

정수 $n$, $f\_{1}$, $f\_{2}$, $f\_{3}$, $c$가 주어진다. $f\_{n} \bmod (10^{9}+7)$을 구하시오.

한 줄에 다섯 정수 $n$, $f\_{1}$, $f\_{2}$, $f\_{3}$, $c$가 주어진다. ($4 \le n \le 10^{18}$, $1 \le f\_{1}$, $f\_{2}$, $f\_{3}$, $c \le 10^{9}$)

$f\_{n} \bmod (10^{9} + 7)$의 값을 출력한다.

첫 번째 예제에서 $f\_{4} = 90$, $f\_{5} = 72900$이다.

두 번째 예제에서 $f\_{17} \approx 2.28 \times 10^{29587}$이다.