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