격자 위의 로봇

격자의 왼쪽 위 칸에서 오른쪽 아래 칸까지 스스로 길을 찾아가는 로봇을 만들었다. 하지만 로봇에는 아주 단순한 논리만 들어 있어서 오른쪽과 아래쪽으로만 이동할 수 있다(어차피 목표가 그 방향에 있다).

장애물이 놓인 격자 위에 로봇을 올려놓고 지켜보다가, 로봇이 자꾸 막히는 모습에 지쳐 이런 질문이 떠올랐다. 출발점에서 도착점까지 가는 서로 다른 경로는 몇 개일까? 그리고 만약 하나도 없다면, 위쪽과 왼쪽으로도 움직일 수 있었다면 도착점에 닿을 수 있었을까?

이제 다음을 계산하는 프로그램을 작성하자. 로봇이 지나갈 수 없는 장애물이 표시된 $n \times n$ 격자가 주어질 때, 왼쪽 위 칸 $s$에서 오른쪽 아래 칸 $t$까지 오른쪽과 아래쪽으로만 이동하는 서로 다른 경로의 수를 센다. 경로의 수가 매우 커질 수 있으므로 답은 $2^{31} - 1$로 나눈 나머지로 출력한다. 그런 경로가 하나도 없다면, 위쪽과 왼쪽 이동까지 허용했을 때 도착점에 닿을 수 있는지 판정한다.

첫째 줄에 정수 $n$이 주어진다($1 \le n \le 1000$).

다음 $n$개의 줄에는 각각 $n$개의 문자가 주어진다. 각 문자는 .(지나갈 수 있는 칸) 또는 #(지나갈 수 없는 칸)이다. 출발 칸 $s$(왼쪽 위)와 도착 칸 $t$(오른쪽 아래)에는 절대 장애물이 놓이지 않는다.

한 줄을 출력한다.

• 오른쪽과 아래쪽 이동만으로 $s$에서 $t$까지 가는 서로 다른 경로의 수를 $2^{31} - 1$로 나눈 나머지, 또는
• 오른쪽·아래쪽만으로는 갈 수 없지만 위쪽·왼쪽 이동까지 허용하면 갈 수 있는 경우 THE GAME IS A LIE, 또는
• $s$에서 $t$로 가는 경로가 전혀 없는 경우 INCONCEIVABLE.