Cho \(f_x = c^{2x - 6} \times f_{x - 1} \times f_{x - 2} \times f_{x - 3}\) với \(x \ge 4\). Hãy tính \(f_n\) lấy dư cho \(10^9 + 7\).

Input

• Gồm một dòng là các số \(n, f_1, f_2, f_3, c\) \((4 \le n \le 10^{18}, 1 \le f_1, f_2, f_3 \le 10^9)\).

Output

• Một số nguyên duy nhất là đáp án của bài toán.

Example

5 1 2 5 3

72900

17 97 41 37 11

317451037