曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5984: 路径计数 II

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：52 Solved：22
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

现在有一个n*m的方格，要求从方格的左上角走到右下角，并且每一步只能向右或向下走。但是方格中有些格子有障碍物无法进入，请问有多少种走法。答案对10^9+7取模。

Input

第一行两个整数n,m
接下来n行，每行用空格隔开的整数，0表示可以走，1表示障碍物

Output

一行一个整数表示答案

Sample Input Copy 

2 2
0 1
0 0

Sample Output Copy 

1

HINT

1 ≤ n, m ≤1000