说明

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