408 : 格子間の許容経路

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

点$(x_1, y_1)$から$(x_2,y_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 を求めよ。