Product Oriented Recurrence

## 题目描述 当 $x \geq 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$ 的值，对 $10^9 + 7$ 取模。 $(4 \leq n \leq 10^{18},1 \leq f_1,f_2,f_3,c \leq 10^9)$ ## 输入输出格式 **输入格式** 共一行，依次输入 $n,f_1,f_2,f_3,c$ 。 **输出格式** 共一行，输出 $f_n \bmod (10^9 + 7)$ 。

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

5 1 2 5 3

72900

17 97 41 37 11

317451037

In the first example, $ f_{4} = 90 $ , $ f_{5} = 72900 $ . In the second example, $ f_{17} \approx 2.28 \times 10^{29587} $ .