---

Problem 662

---

Fibonacci paths

Alice walks on a lattice grid. She can step from one lattice point $A(a,b)$ to another $B(a+x,b+y)$ providing distance $AB=\sqrt{x^2+y^2}$ is a Fibonacci number $1,2,3,5,8,13,\dots$ and $x\ge 0,$ $y\ge 0$.

In the lattice grid below Alice can step from the blue point to any of the red points.

Let $F(W,H)$ be the number of paths Alice can take from $(0,0)$ to $(W,H)$.
You are given $F(3,4)=278$ and $F(10,10)=215846462$.

Find $F(10,000,10,000)mod1,000,000,007$.

---

斐波那契路径

爱丽丝正在格阵上行走，每次她都可以从一个格点$A(a,b)$走到另一个格点$B(a+x,b+y)$，只要两点间距离$AB=\sqrt{x^2+y^2}$是一个斐波那契数$1,2,3,5,8,13,\dots$，且$x\ge 0$，$y\ge 0$。

如下图的格阵，从蓝点出发，爱丽丝可以前往任意一个红点。

记$F(W,H)$为爱丽丝从$(0,0)$出发到达$(W,H)$的可行路径数目。
已知，$F(3,4)=278$，$F(10,10)=215846462$。

求$F(10,000,10,000)mod1,000,000,007$.

---