解説

${A_N} = a, b, ab, ab^2, a^2b^3, \ldots$ となります。

$N$ 番目のフィボナッチ数を $F_N$ とすると、これを使って $A_N = a^{F_{N-1}} b^{F_N}$ と表せます。

フィボナッチ数は行列累乗によって $O(\log N)$ で計算できます。

$F_N$ の法は $10^9 + 7$ ではなく $10^9 + 6$ であることに注意してください。