Задача 662
Пути Фибоначчи

Алиса ходит по сетке. Она может перейти с одной точки решетки $A (a,b)$ на другую $B (a+x,b+y)$, при условии что расстояние $AB = \sqrt{x^2+y^2}$ является числом Фибоначчи $\{1,2,3,5,8,13,\ldots\}$ и $x\ge 0$, $y\ge 0$.

На решетке ниже Алиса может перейти из синей точки в любую из красных точек.

p662_fibonacciwalks.png

Пусть $F(W,H)$ будет количеством путей, по которым Алиса может перейти из $(0,0)$ в $(W,H)$.
Известно, что $F(3,4) = 278$ и $F(10,10) = 215846462$.

Найдите $F(10\,000,10\,000) \bmod 1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net