Пусть \(f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}\) для \(x \ge 4\).
Вам даны \(n\), \(f_{1}\), \(f_{2}\), \(f_{3}\) и \(c\). Найдите \(f_{n} \bmod (10^{9}+7)\).
Выходные данные
Выведите \(f_{n} \bmod (10^{9} + 7)\).
Примечание
В первом примере \(f_{4} = 90\), \(f_{5} = 72900\).
Во втором примере \(f_{17} \approx 2.28 \times 10^{29587}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2 5 3
|
72900
|
|
2
|
17 97 41 37 11
|
317451037
|