Mô tả và yêu cầu

Đườ ng đi rô-b ố t

B ạn vừa tạo ra mộ t bảng đ ể cho rô-b ốt có th ể tìm đ ườ ng đi từ ô ở trên cùng – bên trái (ô xu ất
phát) đ ến ô ở dướ i cùng – bên ph ải (ô đích). Tuy nhi ên, do quên mấ t mộ t số ski l l A I mà bạn chỉ
lập trình cho rô-b ố t có th ể đi sang ph ải 1 ô ho ặc xu ống d ướ i 1 ô. Bạn đ ặt mộ t số ch ướ ng ng ại vật
trên các ô của b ảng (dĩ nhi ên l à rô-b ốt ko th ể đi vào các ô này), sau đó b ạn ng ồ i quan sát. Tuy
nhi ên, sau mộ t thờ i gi an, bạn cảm th ấ y mệ t mỏ i vì nó bị mắ c kẹ t và b ạn tự h ỏi : “C ó bao nhi êu
đườ ng đi có th ể cho rô-b ốt từ ô xu ấ t phát tớ i ô đích” và “N ế u không có, thì l i ệ u rô-b ố t có thể đ ế n
ô đích n ế u nó đ ượ c lập trình có th ể đi l ên trên 1 ô và sang trái 1 ô”.

V ì vậy, b ạn quyế t đ ịnh vi ết 1 ch ươ ng trình, cho kích th ướ c của b ảng n×n vớ i các ch ướ ng ng ại vật
đã đ ượ c dánh d ấ u mà rô-b ố t không th ể đi tới . Đếm số đườ ng đi khác nhau mà rô-b ố t có thể đi từ
ô xu ấ t phát tớ i ô đích. V à n ế u không có đ ườ ng đi , bạn ph ải kiếm tra xem có th ể đi từ ô xuấ t phát
tới ô đích n ế u có th ể sang trái và l ên trên. Tuy nhi ên, ch ươ ng trình của b ạn không xử l ý các số
rất lớn, do đó, kế t quả ph ải đượ c lấy d ư cho 2^ 31-1.

D ữ liệ u:

D òng đ ầ u ti ên ch ứa mộ t số nguyên n (1 <= n <= 1000).

N dòng sau, mỗ i dòng ch ứa n kí tự đ ại , mỗ i kí tự diện cho mộ t ô của b ảng. K í tự có th ể l à ‘ .’ hoặc
‘ #’ . K í tự ‘ .’ nếu ô đó có thể đi , hoặc ‘ #’ nếu ô đó l à ch ướ ng ng ại vật. K hông có trườ ng h ợ p có
ch ướ ng ng ại vật ở ô xu ất phát và ô đích.

K ế t qu ả:

In ra mộ t dòng ch ứa số nguyên l à số đườ ng đi khác nhau từ ô xu ấ t phát tớ i ô kế t thúc (lấ y d ư
cho 2^ 31-1) ho ặc “TH E GA ME IS A LIE ” n ế u không th ể đi từ ô xuấ t phát tớ i ô kết thúc b ằ ng cách
ch ỉ sang ph ải và xu ống d ướ i nhưng có th ể đi nếu ch ấ p nh ận thêm cách đi l ên trên và sang trái ,
ho ặc IN C ON C E IV A B LE n ế u đ ơ n gi ản l à không có đ ườ ng đi từ ô xu ấ t phát tớ i ô đích.

V í dụ:

IN P U T OU TP U T
5 6

.....

#..#.

#..#.

...#.

.....

IN P U T OU TP U T

IN P U T OU TP U T
7 TH E GA ME IS A LIE

......#

####...

.#.....

.#...#.

.#.....

.#..###

.#.....