EduBrick

Пути в лабиринте

1000 мс · 256 МБ · всё или ничего

В прямоугольной таблице некоторые клетки заняты. Начав в левой верхней клетке и двигаясь только вправо и вниз по свободным клеткам, посчитайте количество способов дойти до правой нижней клетки. Ответ по модулю 109+710^9 + 7.

Формат ввода

В первой строке nn и mm (1≤n,m≤10001 \le n, m \le 1000). В следующих nn строках — по mm символов: точка — свободная клетка, решётка — занятая.

Формат вывода

Выведите количество путей по модулю 109+710^9 + 7.

Примеры

ввод
1 1
.
вывод
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.