CF1182E.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)$.

对于 $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)$。

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

唯一的一行包含五个整数 $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}$）。

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

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

在第一个例子中，$f_{4} = 90$，$f_{5} = 72900$。

在第二个例子中，$f_{17} \approx 2.28 \times 10^{29587}$。