1365: 街道问题2
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 76 Solved: 13
[Status] [Submit] [Creator:]
Description
小图站在曼哈顿的一角，想从所在位置到达曼哈顿另一角，每次只能选择向下或向右走。
但是现在街道上有些地方放置着障碍物，如图中有障碍物为“1”，没有障碍物为“0”。
如图：
但是现在街道上有些地方放置着障碍物，如图中有障碍物为“1”，没有障碍物为“0”。
如图：
Input
第一行n,m (n,m<=5000)
第2行到n+1到，每行m个数，分别为0和1，
第2行到n+1到，每行m个数，分别为0和1，
Output
一个数表示总共的走法！由于数据比较大，答案对10009取模。
Sample Input Copy
3 4
0 0 0 0
0 1 0 0
0 0 0 0
Sample Output Copy
4