E. Product Oriented Recurrencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet 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).InputThe 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}).OutputPrint f_{n} \bmod (10^{9} + 7).ExamplesInput
5 1 2 5 3
Output
72900
Input
17 97 41 37 11
Output
317451037
NoteIn the first example, f_{4} = 90, f_{5} = 72900.In the second example, f_{17} \approx 2.28 \times 10^{29587}.
5 1 2 5 3

72900 
['dp', 'math', 'matrices', 'number theory', '*2300']