リンクについてる解説が結構どれもTLEが厳しそうでしたが、300msぐらいで通ります。

解説

フィボナッチ数列になるのは他の解説を参考にしてください。

ここまでくると求めるのは

$(フィボナッチ数列のC番目) ^ D$ になります。

フィボナッチ数列は普通に行列累乗で求めても高速に求まりますが、一工夫あって実はmod 1'000'000'007では周期が2 * (1'000'000'007 + 1)であることが知られています。

詳しくは

ということで、まずはCを2 * (1'000'000'007 + 1)で割った余りにしてしまいましょう。

次はDに関してですが、フェルマーの小定理から,、 $a$ が1'000'000'007と互いに素なら

$a ^ {1000000006} \mod 1000000007 = 1$

です。よってフィボナッチ数列の $C$ 番目を1'000'000'007で割った余りが0なら0で、そうでないなら $D$ は1'000'000'006で割った余りでやれば大丈夫です。

以上で高速に求めることができました。

提出コード