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

Условие

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

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

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

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

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

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

• Точка '.'(ASCII 46) обозначает пустую клетку
• Решётка '#'(ASCII 35) обозначает стену, в такие клетки заползти нельзя

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

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

Ограничения

1 ≤ N, M ≤ 500

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

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

3 3
...
.#.
...

2

5 3
...
...
#..
.#.
...

6

2 10
........#.
..#.......

0