Дана таблица размера 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 (10⁹ + 7). Два пути называются непересекающимися, если у них есть ровно две общие клетки — начальная и конечная.