Şəbəkədə robotlar

Siz yaxınlarda şəbəkə üzərində hərəkət edə bilən bir robot yaratdınız. Bu robot, şəbəkənin sol üst küncündən sağ alt küncünə yol tapa bilir. Süni intellekt proqramlaşdırma bacarıqlarınızı unutduğunuz üçün robotu yalnız sağa və aşağıya hərəkət edəcək şəkildə proqramlaşdırdınız (bu, əslində məqsəddir). Robotunuzu bəzi maneələrlə dolu bir şəbəkəyə yerləşdirdiniz və onu izləməyə başladınız. Lakin bir müddət sonra robot ilişib qaldı və siz özünüzə sual verdiniz: "Başlanğıc mövqedən son mövqeyə neçə yol var?" və "Əgər belə yollar mövcud deyilsə, robot yuxarı və sola da hərəkət edə bilsə, məqsədə çata bilərmi?"

Siz, şəbəkənin ölçüsünə görə n × n ölçüsündə maneələrlə işarələnmiş (robotun üzərinə çıxa bilmədiyi) bir proqram yazmağa qərar verdiniz. Bu proqram, robotun sol üst küncdən sağ alt küncə neçə yolla keçə biləcəyini hesablayacaq. Əgər bu mümkün deyilsə, onda robotun sola və yuxarı hərəkət etməsinə icazə verildikdə məqsədə çata biləcəyini müəyyən etmək lazımdır. Proqramınız böyük ədədləri emal etmir, buna görə cavabı 2^31 - 1 moduluna görə çıxarmalısınız.

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 1000) dəyərini ehtiva edir. Növbəti n sətirdən hər biri n simvol ehtiva edir, hər biri '.' və ya '#' bərabərdir, burada '.' boş yeri, '#' isə maneə plitəsini göstərir. Başlanğıc s və son t nöqtələrində divar yoxdur.

Çıxış məlumatları

s-dən başlayıb t-də bitən yolların sayını (modul 2^31 - 1 ilə) çıxarın və ya yalnız sağa və aşağıya hərəkət edərək s-dən t-yə çatmaq mümkün deyilsə, lakin dörd tərəfə hərəkət edərək çatmaq mümkündürsə THE GAME IS A LIE və ya s-dən t-yə heç bir yol yoxdursa INCONCEIVABLE çıxarın.