问题描述

具体描述见教材p160： 乐乐有一个棋盘，共有m行n行，一只棋从左上角开始， 向右下角移动， 每次只能向下或向右移动一次。然而这个棋盘中有一些障碍物，这些障碍物使得这个棋子不能进入这些格子，问这个棋子从左上角到达右下角共有多少种不同的移法？ 如果到达不了，则输出0。

格式

输入

第1行，两个整数m,n (0<m, n<=100); 后面有m行，每行有n个数（0或1），如果是1，则表示这个方格中有障碍物。

输出

求得的方案数。

样例

4 5
0 0 1 0 0 
0 1 0 0 0
0 0 0 0 0
0 1 0 0 0

3

3 3 
1 0 1 
1 1 0
0 0 0

0

限制

1s, 64MB.