Robots on a Grid

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.

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.

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.