ProjectEuler 408 Admissible paths thro - 拼圖

408. Admissible paths through a grid

http://projecteuler.net/problem=408


我們稱整數點 ( x , y ) 為「不可容許的點」，如果他的 x、y 還有 x + y 都是正完全

平方數。舉例來說，(9,16) 就是不可容許的點，但 (0,4)、(3,1)、(9,4) 就不是。


再來想一條路徑，起點是 ( x_1 , y_1 )，終點是 ( x_2 , y_2)，走的方法只能用一單位

往北或是一單位往東。如果某條路徑，途中沒有經過不可容許的點，我們則稱這條路徑為

「可容許的路徑」。


使 P(n) 為 (0,0) 到 (n,n) 中可容許的路徑的數量。我們知道 P(5) = 252，P(16) =

596994440，P(1000) mod 1000000007 = 341920854。


請求出 P(10000000) mod 1000000007。

--