\includegraphics{https://static.e-olymp.com/content/64/64ea1b6b30351d386cecedd8b1056ddb69bd8dd9.jpg} Вы недавно создали робота, способного ходить по сетке. Который может найти путь из левого верхнего угла сетки в правый нижний. Вы забыли все Ваши навыки в программировании искусственного интеллекта, поэтому запрограммировали движение робота только вправо и вниз (в этом все-таки и состоит цель). Вы разместили своего робота на сетке с некоторыми препятствиями, и вот сидите и наблюдаете. Однако через некоторое время он застрял, а Вы спросили себя, "\textit{Сколько существует путей из начальной позиции до конечной?}", и "\textit{Если таких путей не существует, сможет ли робот достичь цели если он может двигаться также вверх и влево?}" Вы решили написать программу, которая по размеру сетки \textbf{n}×\textbf{n} с отмеченными на ней препятствиями (на которые робот не может наступать) вычислит количество способов, которыми робот может пройти из левого верхнего угла в нижний правый. Если это невозможно, то следует выяснить, сможет ли робот достигнуть цели если ему разрешено двигаться влево и вверх. Ваша программа не обрабатывает большие числа, поэтому следует вывести ответ по модулю \textbf{2^31 - 1}. \InputFile Первая строка содержит значение \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{1000}). Каждая из следующих \textbf{n }строк содержит \textbf{n }символов, каждый из которых равен '\textbf{.}' или '\textbf{#}', где '\textbf{.}' обозначает пустое место, а '\textbf{#}' - плитка-препятствие. Стена отсутствует на старте \textbf{s} и на финише \textbf{t}. \OutputFile Вывести количество путей начинающихся в \textbf{s} и заканчивающихся в \textbf{t} (по модулю \textbf{2^31 - 1}) или \textbf{THE GAME IS A LIE} если невозможно дойти из \textbf{s} в \textbf{t} двигаясь только вправо и вниз, но можно при движении во все четыре стороны, либо \textbf{INCONCEIVABLE} если не существует пути из \textbf{s} в \textbf{t}.