Problem 408 の変更点

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

*[[Problem 408:http://projecteuler.net/problem=408]] 「格子間の許容経路」 [#k242f6d8]

'''x''', '''y''', そして '''x''' + '''y''' がすべて正の完全平方数であるとき, その格子点 ('''x''', '''y''') を''非許容点''と呼ぼう.~
例えば, (9, 16) は非許容点であり, (0, 4), (3, 1), (9, 4) はそうではない.

点 ('''x'''&sub{1};, '''y'''&sub{1};) から ('''x'''&sub{2};, '''y'''&sub{2};) へ, 北か東への単位ステップのみを使って移動する経路を考えよう.~
もしその経路の途中の点で非許容点を通らないとき, そのような経路を''許容経路''と呼ぼう.

(0, 0) から ('''n''', '''n''') までの許容経路の数を P('''n''') としよう.~
P(5) = 252, P(16) = 596994440, P(1000) mod 1 000 000 007 = 341920854 であることが確かめられる.

P(10 000 000) mod 1 000 000 007 を求めよ.