Robots on a Grid

Interview

Time limit1sMemory limit128 MB

Summary

Count monotone right/down paths from the top-left to the bottom-right of an n by n grid with blocked cells, modulo 2^31-1, and report whether the goal is reachable at all, or reachable only with up and left moves allowed.

Level: Medium5 of 10
Topics: Dynamic programming, DFS, Matrix, Implementation
Solved: No attempts yet

Problem

You have built a grid-traversing robot that finds its way from the top-left corner of a grid to the bottom-right corner. Because it was programmed with very limited logic, the robot can only move right and down (which is, after all, the direction of the goal).

You place the robot on a grid that contains some obstacles and watch it work. After a while you grow tired of seeing it get stuck and start to wonder: how many distinct paths lead from the start to the goal? And, if there are none, could the robot still have reached the goal if it were also allowed to move up and left?

Write a program that, given an $n \times n$ grid with some blocked cells the robot cannot enter, counts the number of distinct ways the robot can travel from the top-left corner $s$ to the bottom-right corner $t$ moving only right and down. Because the count can be enormous, report it modulo $2^{31} - 1$ . If no such path exists, determine whether the goal would be reachable if the robot were also allowed to move up and left.

Input

The first line contains one integer $n$ ( $1 \le n \le 1000$ ).

Each of the next $n$ lines contains $n$ characters. Each character is either . (a walkable cell) or # (a blocked cell). The start cell $s$ (top-left) and the goal cell $t$ (bottom-right) are never blocked.

Output

Print one line:

the number of distinct paths from $s$ to $t$ using only right and down moves, taken modulo $2^{31} - 1$ ; or
THE GAME IS A LIE if there is no such right/down-only path but the goal is reachable when up and left moves are also allowed; or
INCONCEIVABLE if there is no path from $s$ to $t$ at all.

Examples4

Example 1
Input
```
5
.....
#..#.
#..#.
...#.
.....
```
Expected output
```
6
```

Example 2

Input

7
......#
####...
.#.....
.#...#.
.#.....
.#..###
.#.....

Expected output

THE GAME IS A LIE

Example 3
Input
```
1
.
```
Expected output
```
1
```
Example 4
Input
```
2
..
..
```
Expected output
```
2
```