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 を求めよ.