D. Черепашки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Дана таблица размера n × m. Будем считать, что строки таблицы пронумерованы сверху вниз от 1 до n, а столбцы — слева направо от 1 до m. Тогда клетку, находящуюся в строке x и столбце y, будем обозначать (x, y).

Изначально в клетке (1, 1) стоят две одинаковые черепашки. Обе черепашки хотят попасть в клетку (n, m). В некоторых клетках таблицы существуют препятствия, но гарантируется, что в левом верхнем и правом нижнем углах их нет. Из клетки (x, y) черепашка (как одна, так и другая) может перейти в одну из двух клеток (x + 1, y) и (x, y + 1), если соответствующая клетка не содержит препятствия. Черепашки поссорились, поэтому они не хотят, чтобы на протяжении пути была хоть какая-то вероятность встретиться. Помогите им найти количество способов, которыми они могут пройти от клетки (1, 1) до клетки (n, m).

Более формально, найдите количество пар непересекающихся путей из клетки (1, 1) в клетку (n, m) по модулю 1000000007 (109 + 7). Два пути называются непересекающимися, если у них есть ровно две общие клетки — начальная и конечная.

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

В первой строке записаны два целых числа n, m (2 ≤ n, m ≤ 3000). В каждой из следующих n строк записано m символов — описание таблицы. Свободные клетки обозначаются символом «.», клетки с препятствиями — символом «#».

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

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

В единственной строке выведите целое число — количество пар непересекающихся путей из клетки (1, 1) в клетку (n, m) по модулю 1000000007 (109 + 7).

Примеры
Входные данные
4 5
.....
.###.
.###.
.....
Выходные данные
1
Входные данные
2 3
...
...
Выходные данные
1