题目描述

乐乐有一个棋盘，共有 $m$ 行 $n$ 列，一只棋子从左上角开始，向右下角移动，每次只能向下或向右移动一次。

然而这个棋盘中有一些障碍物，这些障碍物使得这个棋子不能进入这些格子，问这个棋子从左上角到达右下角共有多少种不同的移法？如果到达不了，则输出 $0$ 。

输入格式

第一行：两个整数 $m$，$n$ ($0 \lt m，n \le 100$)

后面有 $m$ 行，每行有 $n$ 个数( $0$ 或 $1$ )，如果是 $1$ ，则表示这个方格中有障碍物。

数据范围

对于 80% 的数据，$0 \lt m ，n \lt 20$ ；

对于 100% 的数据，$0 \lt m，n \le 100$ 。

输出格式

求得的方案数。

样例

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