11486 - Finding Paths in Grid

[quol]

Hello,
can anyone give me a hint how to solve this problem effectively?

Here's what I tried:

For the 840 possible states I calculated the adjacency matrix.
Then I used matrix multiplication to precalculate the number of paths of length 2^1 ... 2^30 from each state to each state.

Then for each test case I multiplicated the precalculated matrices to calculate the number of paths.

Even though this solution runs in O(log n) time, of course it is way to slow, as multiplicating two matrices of size 840x840 takes 840^3 steps (using the primitive approach).

[emotional blind]

Number of possible states is less than 840.