Пути в сетке с препятствиями

Условие

В первой строке даны n и m. В каждой из следующих n строк даны m чисел: 0 — свободная клетка, 1 — препятствие. Выведите число путей из левой верхней клетки в правую нижнюю, если ходить можно только вправо или вниз и нельзя заходить на препятствия, по модулю 10^9 + 7. Если стартовая или конечная клетка занята, ответ 0.

Примеры

3 3
0 0 0
0 1 0
0 0 0

2

1 1
0

1

Ограничения

• 1 ≤ n, m ≤ 300