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

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