Задача B. Черепаха в лабиринте

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Черепаха Тортила любит исследовать лабиринты: она ползает по лабиринту и считает количество вариантов, которыми можно проползти лабиринт с левого нижнего угла в правый верхний.Тортила умеет ползать только вверх, вправо и влево, и в каждую клетку может вползти только один раз.

Недавно черепаха купила компьютер, и хочет по описанию лабиринта быстро рассчитывать количество способов, которыми можно добраться с левого нижнего в правый верхний угол, проползая через каждую клетку не больше одного раза.

Вам нужно написать программу для черепахи Тортилы.

Формат входного файла

В первой строке входного файла содержатся числа N M

В следующих далее N строчек по M символов содержится описание лабиринта:

Формат выходного файла

В выходном файле должно содержаться единственное число — количество способов, которыми можно добраться с левого нижнего в правый верхний угол, проползая через каждую клетку не больше одного раза.

Ограничения

1 ≤ N, M ≤ 500

Гарантируется, что левый нижний и правый верхний углы лабиринта — пустые клетки

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
...
.#.
...
2
2
5 3
...
...
#..
.#.
...
6
3
2 10
........#.
..#.......
0

0.036s 0.007s 15