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