Problem 416 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 416 へ行く。

*[[Problem 416:http://projecteuler.net/problem=416]] 「カエルの旅行」 [#j58a5d32]

一番左のマスにカエルがいる '''n''' 個のマスの列がある. 連続してジャンプすることにより, カエルは一番右のマスに移動し, 再び一番左のマスに戻ってくる. 下り(最初のマスから離れる方へ向かう)のときはカエルは右へ1マス, 2マス, あるいは3マスジャンプする, そして上り(最初のマスへ近づく方へ向かう)の時は同様にして左にジャンプする. カエルはマスの外には移動できない. カエルはこの往復を '''m''' 回繰り返す.

訪れることのないマスをたかだかひとつだけ残してカエルが旅行できる方法の数を F('''m''', '''n''') としよう.

例えば, F(1, 3) = 4, F(1, 4) = 15, F(1, 5) = 46, F(2, 3) = 16, そして F(2, 100) mod 10&sup{9}; = 429619151 となる.

F(10, 10&sup{12};) の末尾9桁を求めよ.