問題文

数列 ANA_N

A0=aA1=bAN=AN2AN1(N2)\begin{aligned} A_0 &= a \\ A_1 &= b \\ A_N &= A_{N - 2} A_{N - 1} & (N \ge 2) \end{aligned}

と定義します。

整数 N,a,bN, a, b に対して、 ANmod109+7A_N \mod 10^9 + 7 を求めてください。

制約

  • 0N10180 \le N \le 10^{18}
  • 0a,b10180 \le a, b \le 10^{18}
  • 入力は全て整数である

入力

N a bN\ a\ b

出力

答えを 11 行に出力せよ。

入出力例

入力例1
2 2 3
出力例1
6

AN=2,3,6,18,{A_N} = 2, 3, 6, 18, \ldots となり、 A2=6A_2 = 6 です。

Submit


Go (1.21)