Вы находитесь в левой верхней клетке \((1, 1)\) лабиринта размера \(n \times m\) клеток. Ваша цель — попасть в правую нижнюю клетку \((n, m)\). Вы можете двигаться только вправо и вниз по одной клетке за ход. Переход вправо из клетки \((x, y)\) ведёт в клетку \((x, y + 1)\), а переход вниз — в клетку \((x + 1, y)\).
В некоторых клетках лабиринта лежат камни. Когда вы перемещаетесь в клетку с камнем, камень сдвигается в следующую клетку по направлению движения. Если в следующей клетке также есть камень, он сдвигается дальше в том же направлении, и так далее.
Лабиринт окружён непроницаемыми стенами, поэтому ходы, в результате которых вы или камень выходят за границы лабиринта, невозможны.
Вычислите количество различных способов добраться от старта до цели по модулю \(10^9 + 7\). Два способа считаются различными, если существует клетка, посещённая в одном из способов, но не посещённая в другом.
Выходные данные
Выведите одно целое число — количество различных способов добраться из клетки \((1, 1)\) в клетку \((n, m)\) по модулю \(10^9 + 7\).
Примечание
В первом примере нам нельзя (и не нужно) двигаться, поэтому единственный способ добраться посещает единственную клетку \((1, 1)\).
Во втором примере цель заблокирована и в неё нельзя попасть.
Иллюстрации к третьему примеру можно найти здесь: https://cfassets.m27.workers.dev/rounds/1225/index.html
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
.
|
1
|
|
2
|
2 3
...
..R
|
0
|
|
3
|
4 4
...R
.RR.
.RR.
R...
|
4
|