ловие

На складе робот перемещается по прямоугольной сетке размером m x n. Некоторые ячейки заняты, и заезжать в них нельзя.

Каждая ячейка описывается числом:

• 0 — свободная ячейка;
• 1 — занятая ячейка.

Робот стартует в левой верхней ячейке и должен добраться в правую нижнюю. За один ход он может переместиться только:

• на одну ячейку вправо;
• на одну ячейку вниз.

Робот не может заезжать в занятые ячейки.

Требуется определить количество различных маршрутов из стартовой ячейки в конечную по модулю 1000000007.

Если ячейка занята, количество маршрутов через неё считается равным 0.

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

Первая строка содержит два целых числа m и n — размеры сетки.

В следующих m строках записано по n чисел 0 или 1, задающих схему склада.

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

Выведите одно число — количество возможных маршрутов робота по модулю 1000000007.

Ограничения

• 1 <= m, n <= 1000
• используется только стандартный ввод и стандартный вывод

Примеры

Пример 1

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

3 3
0 0 0
0 1 0
0 0 0

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

2

Пояснение

Центральная клетка заблокирована; остаётся 2 пути в обход.

Пример 2

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

1 1
0

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

1

Пример 3

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

2 2
0 1
0 0

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

1