Cho lưới ô vuông hình chữ nhật ~m \times n~, mỗi ô chỉ chứa một giá trị 0 hoặc 1. Có bao nhiêu cách khác nhau để đi từ ô ~(1,1)~ đến ô ~(m, n)~.

Biết rằng mỗi lần đi chỉ được đi xuống dưới (từ ô ~(i, j)~ đến ô ~(i+1, j)~) hoặc sang phải (từ ô ~(i, j)~ đến ô ~(i, j+1)~) và không được đi vào ô có giá trị 1 (kể cả ô xuất phát ~(1,1)~).

Input

• Dòng đầu là 2 số nguyên dương ~m~ và ~n~ (~m, n \le 50~).
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số (0 hoặc 1) viết liền nhau của một hàng trong bảng.

Output

Ghi ra số đường đi khác nhau tìm được.

Sample Input 1

3 4
0001
0100
0000

Sample Output 1

3

Subtasks

• Subtask 1: Có 60% số test ~n, m \le 30~.
• Subtask 2: Có 40% số test ~n, m \le 50~.