说明

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