Попытка к бегству

Узник пытается бежать из замка, который состоит из N∗M квадратных комнат, расположенных в виде прямоугольника N∗M. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в левой верхней комнате и для ему надо попасть в противоположную правую нижнюю комнату. Времени у него немного, всего он может побывать не более, чем в N+M−1 комнате на своем пути. Определите количество маршрутов, которые ведут к выходу.

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

Первая строчка входных данных содержит натуральные числа N и M, не превосходящие 1000. Далее идет план замка в виде N строчек из M чисел в каждой. Одно число соответствует одной комнате: 1 означает, что в комнату можно попасть, 0 – что комната закрыта.

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

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N−1 комнату, или слово Impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2∗10^9.

Примеры
Ввод
3 5
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
Вывод
3

RABOTAY    2   04.04.2020 12:06    91