>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムでO(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。