题目描述

一个机器人位于一个 $m$ 行 $n$ 列网格 $a$ 的左上角 $(1， 1)$。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角 $(m, n)$。但是网格上有一些障碍，如果 $a_{i, j}=1$ 说明这个格子是障碍，无法通过，否则可以正常通过。不保证起点或者终点不是障碍，如果起点是障碍，机器人将被困在原地，如果终点是障碍，机器人将无法到达终点。

请问一共有多少种不同的路径？

输入格式

输入两个整数 $m$, $n$

接下来 $m$ 行，每行 $n$ 个整数，代表 $a_{i, j}$

输出格式

输出一个整数表示答案，保证答案在int范围内。

样例

3 3
0 0 0
0 1 0 
0 0 0

2

样例1图示

2 2
0 1
0 0

1

样例二图示

数据范围

对于 $100\%$ 的数据，$1 \leq m, n \leq 100$，$a_{i, j}\in\{0,1\}$