Problem 490 の変更点

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

*[[Problem 490:http://projecteuler.net/problem=490]] 「ジャンプするカエル」 [#r5058375]

ある池に '''n''' 個の石があり, 1 から '''n''' まで番号付けされている. 石は連続して1単位ごと間隔を置いて配置されている.

カエルが1の石に座っている. カエルはそれぞれの石を一度だけ訪れて, '''n''' の石で止まりたい. しかし, カエルは一つの石から別の石へは高々3単位離れたところにのみジャンプできる. 言い換えると, '''i''' の石からカエルは 1 ≤ '''j''' ≤ '''n''' となるような '''j''' の石に到達できるとすると, '''j''' は集合 {'''i'''-3, '''i'''-2, '''i'''-1, '''i'''+1, '''i'''+2, '''i'''+3} の要素となる.

カエルが行える移動方法の数を f('''n''') としよう. 例えば, 以下に示すように, f(6) = 14 となる:~
1 → 2 → 3 → 4 → 5 → 6~
1 → 2 → 3 → 5 → 4 → 6~
1 → 2 → 4 → 3 → 5 → 6~
1 → 2 → 4 → 5 → 3 → 6~
1 → 2 → 5 → 3 → 4 → 6~
1 → 2 → 5 → 4 → 3 → 6~
1 → 3 → 2 → 4 → 5 → 6~
1 → 3 → 2 → 5 → 4 → 6~
1 → 3 → 4 → 2 → 5 → 6~
1 → 3 → 5 → 2 → 4 → 6~
1 → 4 → 2 → 3 → 5 → 6~
1 → 4 → 2 → 5 → 3 → 6~
1 → 4 → 3 → 2 → 5 → 6~
1 → 4 → 5 → 2 → 3 → 6~

他の例として, f(10) = 254, そして f(40) = 1439682432976.

1 ≤ '''n''' ≤ '''L''' に対し S('''L''') = ∑ f('''n''')&sup{3}; としよう.~
例えば:~
S(10) = 18230635~
S(20) = 104207881192114219~
S(1 000) mod 10&sup{9}; = 225031475~
S(1 000 000) mod 10&sup{9}; = 363486179~

S(10&sup{14};) mod 10&sup{9}; を求めよ.