Вы недавно создали робота, способного ходить по сетке. Который может найти путь из левого верхнего угла сетки в правый нижний. Вы забыли все Ваши навыки в программировании искусственного интеллекта, поэтому запрограммировали движение робота только вправо и вниз (в этом все-таки и состоит цель). Вы разместили своего робота на сетке с некоторыми препятствиями, и вот сидите и наблюдаете. Однако через некоторое время он застрял, а Вы спросили себя, "Сколько существует путей из начальной позиции до конечной?", и "Если таких путей не существует, сможет ли робот достичь цели если он может двигаться также вверх и влево?"

Вы решили написать программу, которая по размеру сетки n × n с отмеченными на ней препятствиями (на которые робот не может наступать) вычислит количество способов, которыми робот может пройти из левого верхнего угла в нижний правый. Если это невозможно, то следует выяснить, сможет ли робот достигнуть цели если ему разрешено двигаться влево и вверх. Ваша программа не обрабатывает большие числа, поэтому следует вывести ответ по модулю 231 - 1.

Входные данные

Первая строка содержит значение n (1 ≤ n ≤ 1000). Каждая из следующих n строк содержит n символов, каждый из которых равен '.' или '#', где '.' обозначает пустое место, а '#' - плитка-препятствие. Стена отсутствует на старте s и на финише t.

Выходные данные

Вывести количество путей начинающихся в s и заканчивающихся в t (по модулю 231 - 1) или THE GAME IS A LIE если невозможно дойти из s в t двигаясь только вправо и вниз, но можно при движении во все четыре стороны, либо INCONCEIVABLE если не существует пути из s в t.