880061 - 调皮的猫咪

通过次数

25

提交次数

42

时间限制 : 1 秒
内存限制 : 128 MB

皮皮的猫咪又一次越狱了,目标是远处的冰激凌商店,由于猫咪之前越狱已经积累了不少的经验,于是这次猫咪逃的更快了,如果皮皮想要寻找猫咪,相当于身处在一个地图中,地图上有一些部分可以正常通行,而另一些部分则不能通过。皮皮目前的位置在地图的左上角,他知道猫咪会逃到地图右下角的冰激凌商店。皮皮想要在路上截住猫咪。为了防止走冤枉路,皮皮的每一步只会向右或者向下行走。皮皮想知道,有多少条通往冰激凌商店的路径呢?

输入

输入由 n+1 行组成;

第一行,为两个整数 n 和 m(0<n<m<=20)
第二行至第 n+1 行,每行有 m 个整数,第 i 行第 j 列的整数代表地图上的坐标为(i,j)的点是否可以通过,1 表示该点可以通过,0 表示该店不能通过(数据保证起点和终点是可以通过的)

输出

输出一个正整数,代表皮皮走到冰激凌商店的可行路径数

样例

输入

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

输出

7