← 返回题目列表

Codeforces · 1182/E

E. 面向产品的重复

中文机器翻译题面 查看原题

设 $$$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)$$$。

输入

唯一一行包含五个整数 $$$n$$$、$$$f_{1}$$$、$$$f_{2}$$$、$$$f_{3}$$$ 和 $$$c$$$ ($$$4 \le n \le 10^{18}$$$、$$$1 \le f_{1}$$$, $$$f_{2}$$$、$$$f_{3}$$$、$$$c \le 10^{9}$$$)。

输出

打印 $$$f_{n} \bmod (10^{9} + 7)$$$。

示例

输入 #1

5 1 2 5 3

输出 #1

72900

输入 #2

17 97 41 37 11

输出 #2

317451037

注意

在第一个示例中,$$$f_{4} = 90$$$,$$$f_{5} = 72900$$$。

在第二个示例中,$$$f_{17} \approx 2.28 \times 10^{29587}$$$。