数列 ANA_NAN を
A0=aA1=bAN=AN−2AN−1(N≥2)\begin{aligned} A_0 &= a \\ A_1 &= b \\ A_N &= A_{N - 2} A_{N - 1} & (N \ge 2) \end{aligned}A0A1AN=a=b=AN−2AN−1(N≥2)
と定義します。
整数 N,a,bN, a, bN,a,b に対して、 ANmod 109+7A_N \mod 10^9 + 7ANmod109+7 を求めてください。
N a bN\ a\ bN a b
答えを 111 行に出力せよ。
2 2 3
6
AN=2,3,6,18,…{A_N} = 2, 3, 6, 18, \ldotsAN=2,3,6,18,… となり、 A2=6A_2 = 6A2=6 です。