No.534

フィボナッチ数列を法 $m$ の剰余環上で計算すると必ず周期性がある.

$m \equiv \pm 2 \pmod 5$ のときは周期は $2m+2$ であることが知られている…らしい.

ここまで分かれば, $fib(fib(n)) = fib(fib(n)\ mod\ (2 \cdot 10^9 + 16))$ を求めればいいことがわかる.

大きな数のフィボナッチ数は行列の繰り返し2乗法を使う.