C 旅行

Time Limit: 1000 ms Memory Limit: 32768 KiB

Problem Description

TomAlice结婚一段时间了,感情非常好,一天他们相约去旅行,终点在遥远的地方。

       地形是非常复杂的,路途是非常曲折的。但我们简化一下是一个矩阵。起点也就是他们家在矩阵的左下角,终点也就是他们要去的遥远的地方在右上角,矩阵行列的交点是他们可以驻足的地方,但是有的却是陷阱,他们是不能从那里通过的。Tom要听Alice的,只会往上或往右走,不往回走,直到终点。

       AliceTom提前算出从起点到终点一共有多少条路,可Tom不会啊,所以就找到你了,你是编程高手,希望你帮他解决这个问题,不然他们的婚姻就有危机了。

Input

    输入数据的第一行是两个正整数HW(2 < HW < 20),代表矩阵的高和宽。接下来是一个矩阵,共H行,每行W个元素,用空格隔开,元素取值只有010表示可以走,1表示是陷阱,数据保证位于起点和终点的元素肯定是0

Output

    输出一个整数,即从起点到终点的路径数。

Sample Input

5 5
1 1 1 1 0
0 0 1 1 0
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0

Sample Output

2

Hint


Source

tongjiantao