Роботи на сітці
Ви нещодавно створили робота, здатного пересуватися по сітці. Він може знайти шлях з лівого верхнього кута сітки до правого нижнього. Ви забули всі свої навички програмування штучного інтелекту, тому запрограмували робота рухатися лише вправо і вниз (що, власне, і є метою). Ви розмістили робота на сітці з деякими перешкодами і спостерігаєте за ним. Однак через деякий час він застряг, і ви задумалися: "Скільки існує шляхів з початкової позиції до кінцевої?" і "Якщо таких шляхів не існує, чи зможе робот досягти мети, якщо він може рухатися також вгору і вліво?"
Ви вирішили написати програму, яка для сітки розміром n × n з відміченими на ній перешкодами (на які робот не може наступати) обчислить кількість способів, якими робот може пройти з лівого верхнього кута до правого нижнього. Якщо це неможливо, потрібно з'ясувати, чи зможе робот досягти мети, якщо йому дозволено рухатися вліво і вгору. Ваша програма не обробляє великі числа, тому слід вивести відповідь за модулем 2^31 - 1.
Вхідні дані
Перший рядок містить значення n (1 ≤ n ≤ 1000). Кожен з наступних n рядків містить n символів, кожен з яких дорівнює '.' або '#', де '.' позначає порожнє місце, а '#' - плитка-перешкода. Перешкоди відсутні на старті s і на фініші t.
Вихідні дані
Виведіть кількість шляхів, що починаються в s і закінчуються в t (за модулем 2^31 - 1), або THE GAME IS A LIE, якщо неможливо дійти з s в t, рухаючись тільки вправо і вниз, але можна при русі в усі чотири сторони, або INCONCEIVABLE, якщо не існує жодного шляху з s в t.