SP9652 ROBOTGRI - Robots on a grid

你最近制作了一个机器人，它可以在网格中从左上角移动到右下角。不过，由于你忘记了所有的人工智能编程技能，所以这个机器人只能向右或向下移动（毕竟目标就在那边）。你把机器人放在一个带有一些障碍物的网格上观察，但它总是被卡住。于是你开始思考：「从起始位置到目标位置究竟有多少条路径呢？」还有，「如果没有路径，如果机器人能够向上和向左移动，它是否可以到达目标？」于是，你决定编写一个程序。给定一个 $n \times n$ 的网格，其中某些位置有障碍物，机器人不能经过这些位置，该程序需要计算从左上角出发到右下角的不同路径数。如果没有路径，也要判断如果机器人可以向上和向左移动时，是否有可能到达目标。不过，你的程序处理不了特别大的数字，因此答案需要取模 $2^{31} - 1$。

第一行是一个整数 $1 < n \leq 1000$。接下来有 $n$ 行，每行 $n$ 个字符，每个字符是 `.` 或 `#`。其中 `.` 表示可以行走的格子，`#` 表示不可行走的障碍物。起始点 $s$ 和终点 $t$ 处一定没有障碍物。

输出一行，表示从起点 $s$ 到终点 $t$ 的不同路径数（结果取模 $2^{31} - 1$）。如果只能向右和向下走无法从 $s$ 到 $t$，但如果可以向上和向左走则可以到达目标，则输出 `THE GAME IS A LIE`。如果根本不存在从 $s$ 到 $t$ 的路径，则输出 `INCONCEIVABLE`。 **本翻译由 AI 自动生成**