PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
Suppose that the robot always takes the “right” move at first. We could easily see that a way of robot reaching cell (N, N) is just a set of cells in which the robot takes “turns”. This set is chosen by selecting a combination of K/2 column indices and (K-1)/2 row indices among N-2 indices each dimension. It is easily computed by formula C(K/2, N-2) * C((K-1)/2, N-2). At last, we double the result of this formula to get the last result (because the table is a square one so it is totally the same in case the robot takes the “down” move at first).
The last problem is compute the Combination formula as fast as possible. In this case we have to compute the result modulo 1,000,000,007 which is a prime, so we just use a power function to fast compute that (in logarithmic time).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.