Nhảy cóc trên lưới

Trong một chuyến tham quan bảo tàng, FullHouse Dev được giới thiệu một trò chơi cổ đại thú vị. Đó là một trò chơi nhảy cóc trên một tấm lưới, nơi người chơi phải tìm ra tất cả các cách có thể để di chuyển từ điểm xuất phát đến đích.

Bài toán

Bạn được cho một lưới kích thước \(n \times m\), trong đó mỗi ô chứa giá trị 0 hoặc 1. Một ô bị chặn nếu giá trị của nó là 1. Khi đứng tại một ô, bạn có thể thực hiện các bước di chuyển sau:

• Di chuyển sang phải đến ô không bị chặn gần nhất
• Di chuyển xuống dưới đến ô không bị chặn gần nhất

Xuất phát từ ô \((1,1)\), hãy xác định số cách có thể để đến được ô \((n,m)\).

Do kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) - số hàng và số cột của lưới.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi độ dài \(m\) gồm các ký tự '0' và '1'.

OUTPUT FORMAT:

• In ra một số nguyên duy nhất là số cách để đi từ ô \((1,1)\) đến ô \((n,m)\) theo modulo \(10^9 + 7\).

Ràng buộc:

• \(1 \leq n, m \leq 1000\)
• Mỗi ô chỉ chứa ký tự '0' hoặc '1'

Ví dụ

INPUT

3 3
000
011
000

OUTPUT

3

Giải thích

Có 3 cách để đi từ ô (1,1) đến ô (3,3):

1. (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)
2. (1,1) -> (1,2) -> (3,2) -> (3,3)
3. (1,1) -> (1,2) -> (1,3) -> (3,3)