Detailed mathematical approach

Problem Summary

We must count directed lattice paths from \((0,0)\) to \((w,h)\). Every step is a nonzero vector \((a,b)\in \mathbb{Z}_{\ge 0}^2\) whose Euclidean length is a Fibonacci number, so each admissible move satisfies

$a^2+b^2=F_k^2$

for some Fibonacci number \(F_k\). The answer is required modulo \(10^9+7\).

The main difficulty is that the step set is neither purely local nor regular. Horizontal and vertical Fibonacci jumps are always possible when they fit inside the rectangle, while off-axis moves only appear when a Fibonacci number is also the hypotenuse of an integer right triangle, such as \((3,4)\) for length \(5\).

Mathematical Approach

Let \(D(x,y)\) denote the number of admissible paths from the origin to \((x,y)\). The solution has two layers: first enumerate all legal step vectors, then evaluate an acyclic dynamic program over the grid.

Step 1: Restrict the Relevant Fibonacci Lengths

Any usable step must satisfy \(0\le a\le w\) and \(0\le b\le h\). Therefore its length cannot exceed the diagonal of the target rectangle:

$R=\left\lfloor\sqrt{w^2+h^2}\right\rfloor.$

Only Fibonacci numbers \(F_k\le R\) can matter. This immediately makes the geometric preprocessing finite and small, because the Fibonacci sequence grows exponentially.

Step 2: Enumerate the Admissible Step Vectors

Define the step set

$S=\left\{(a,b)\in \mathbb{Z}_{\ge 0}^2\setminus\{(0,0)\}: a^2+b^2=F_k^2 \text{ for some } F_k\le R\right\}.$

For each relevant Fibonacci number \(F_k\), we search for all nonnegative integer lattice points on the circle \(a^2+b^2=F_k^2\) that also satisfy \(a\le w\) and \(b\le h\). Axis-aligned moves \((F_k,0)\) and \((0,F_k)\) appear automatically when they fit. Additional moves come from Pythagorean triples.

After sorting and deduplication, split \(S\) into

$V=\{d\ge 1:(0,d)\in S\},\qquad O=\{(a,b)\in S:a>0\}.$

The set \(V\) contains the purely vertical moves, while \(O\) contains everything that advances in the \(x\)-direction, including horizontal moves.

Step 3: Write the Global Recurrence

The path count satisfies the direct recurrence

$D(x,y)=\sum_{\substack{(a,b)\in S\\a\le x,\ b\le y}} D(x-a,y-b),\qquad D(0,0)=1.$

This is valid because every admissible path reaching \((x,y)\) has a well-defined final step, and removing that final step leaves a path to \((x-a,y-b)\). Since \(a\) and \(b\) are never both zero, every dependency points strictly left, strictly down, or both. The state graph is therefore acyclic.

Step 4: Separate Earlier Columns from the Current Column

The only awkward part is that vertical moves have \(a=0\), so they stay inside the same column. For a fixed column \(x\), define the contribution from all moves that come from earlier columns:

$A_x(y)=\sum_{\substack{(a,b)\in O\\a\le x,\ b\le y}} D(x-a,y-b).$

Once \(A_x(y)\) is known, the current column can be filled from bottom to top using

$D(x,y)=A_x(y)+\sum_{\substack{d\in V\\d\le y}} D(x,y-d),$

with one extra \(1\) added at \((x,y)=(0,0)\) for the empty path. This transforms the two-dimensional recurrence into a clean sweep: all non-vertical steps are accumulated first, then vertical steps are resolved in increasing \(y\) order within the same column.

Step 5: Keep Only a Sliding Window of Columns

Let

$M=\max\{a:(a,b)\in O\},$

with the convention \(M=0\) if no such step exists. A transition into column \(x\) can only read columns \(x-1,x-2,\dots,x-M\). Anything older is irrelevant. So instead of storing the whole \((w+1)\times(h+1)\) table, it is enough to store columns modulo \(M+1\). This is exactly why a ring buffer is correct.

Worked Example: \((w,h)=(3,4)\)

Here the diagonal length is

$R=\sqrt{3^2+4^2}=5,$

so the relevant Fibonacci lengths are \(1,2,3,5\). The admissible steps are

$V=\{1,2,3\},\qquad O=\{(1,0),(2,0),(3,0),(3,4)\}.$

Column \(x=0\) is determined only by vertical moves:

$D(0,0)=1,\quad D(0,1)=1,\quad D(0,2)=2,\quad D(0,3)=4,\quad D(0,4)=7.$

For \(x=1\), the only non-vertical source is \((1,0)\), so \(A_1(y)=D(0,y)\). After adding vertical continuations we get

$D(1,0)=1,\quad D(1,1)=2,\quad D(1,2)=5,\quad D(1,3)=12,\quad D(1,4)=26.$

For \(x=2\), the source term is \(A_2(y)=D(1,y)+D(0,y)\), which yields

$D(2,0)=2,\quad D(2,1)=5,\quad D(2,2)=14,\quad D(2,3)=37,\quad D(2,4)=89.$

For \(x=3\), we add contributions from \((1,0)\), \((2,0)\), \((3,0)\), and the diagonal step \((3,4)\) from the origin. The final value becomes

$D(3,4)=278,$

which matches the small checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical pipeline. They first generate Fibonacci numbers up to \(R\), then enumerate every admissible pair \((a,b)\) by scanning \(a\) and checking whether \(F_k^2-a^2\) is a perfect square. After sorting and deduplicating the pairs, they store vertical moves separately from moves with positive \(x\)-advance, and they record the largest horizontal component \(M\).

The dynamic program then processes columns from \(x=0\) to \(x=w\). For each column, a temporary array accumulates every contribution coming from earlier columns. After that, the column itself is filled from \(y=0\) upward, so same-column vertical dependencies are already available when needed. The C++ and Java implementations execute this recurrence directly, while the Python implementation reuses the same native computation and returns the parsed final value. In every case, all arithmetic is reduced modulo \(10^9+7\).

Complexity Analysis

Let \(s_O=|O|\), \(s_V=|V|\), and \(M=\max\{a:(a,b)\in O\}\). Generating Fibonacci numbers costs \(O(\log R)\), and enumerating candidate steps costs

$O\left(\sum_{F_k\le R}\min(F_k,w)\right),$

which is modest because the Fibonacci sequence grows exponentially. The dominant part is the grid DP: each column applies every non-vertical step across the valid \(y\)-range and then applies every vertical step while sweeping upward. Thus the running time is

$O\bigl((w+1)(h+1)(s_O+s_V)\bigr),$

and the memory usage is

$O\bigl((M+1)(h+1)\bigr),$

plus one extra temporary array of length \(h+1\).

Footnotes and References

1. Problem page: Project Euler 662
2. Fibonacci numbers: Wikipedia - Fibonacci number
3. Pythagorean triples: Wikipedia - Pythagorean triple
4. Dynamic programming: Wikipedia - Dynamic programming
5. Circular buffer: Wikipedia - Circular buffer