30165번 - Product Oriented Recurrence 다국어

문제

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}$.