Summoner’s Rift là một địa điểm có kết cấu rất kỳ lạ. Được biết địa điểm này có kết cấu là một bảng ~n~ hàng và ~m~ cột, các hàng được đánh số từ ~1~ tới ~n~, các cột được đánh dấu từ ~1~ tới ~m~. Được biết ở đây có một số ô là ô cấm, có nghĩa là ô này không được đi vào.

Có một con Cua kỳ cục đang đứng ở ô ~(1, 1)~, nó đang muốn đi tới ô ~(n, m)~. Nếu Cua kỳ cục đang đứng ở ô ~(u, v)~ thì nó có thể di chuyển tới ô ~(u + 1, v)~ hoặc ~(u, v + 1)~, và nó phải đảm bảo tại mọi lúc thì ô nó di chuyển tới không phải là ô cấm và không nằm ngoài Summoner’s Rift.

Mặc dù đã biết rằng mọi con đường đều dẫn tới Summoner’s Rift nhưng mà chú Cua kỳ cục của chúng ta vẫn muốn biết có bao nhiêu cách để đi từ ô ~(1, 1)~ đến ô ~(n, m)~.

Biết rằng hai cách đi ~S_1, S_2, S_3, S_4,..., S_x~, ~T_1, T_2, T_3, T_4, ..., T_y~ được gọi là khác nhau nếu:

• ~x \neq y~.
• ~\exists i, 1 \leq i \leq \max(x, y), S_i \neq T_i~.

Các bạn hãy giúp Cua kỳ cục nhá.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ lần lượt là số hàng và cột của bảng.
• ~n~ dòng tiếp theo mỗi dòng chứa một chuỗi gồm ~m~ ký tự. Gọi ký tự thứ ~j~ ở hàng ~i~ là ~a_{i, j}~. ~a_{i, j}~ có giá trị là ~1~ thì có nghĩa ô này là ô cấm, và ngược lại.

Output

• Gồm một dòng duy nhất là số cách để Cua kỳ cục đi đến ô ~(n, m)~.
• Và vì con Cua này rất kỳ cục nên nó muốn bạn đưa ra phần dư của kết quả khi chia cho ~10^9 + 22071997~.

Constraint

• ~2 \leq n, m \leq 10^6~.
• ~n \times m \leq 10^6~.
• Dữ liệu đảm bảo ô ~(1, 1)~ và ô ~(n, m)~ không phải ô cấm.

Subtask

• Subtask 1 (25%): ~n, m \leq 4~.
• Subtask 2 (25%): ~n, m \leq 10^3~.
• Subtask 3 (50%): không có giới hạn gì thêm.

Sample Input

2 2
00
00

Sample Output

2