Description

现在有一个n*m的网格
你站在坐标为（1,1）的点
你需要走到坐标为（n,m）的点
假设你当前在点（x,y）你每次只能
走到(x+1,y)或者(x,y+1)
然而有些点是不可以经过的
求方案数
答案对100007取模

Format

Input

第一行两个正整数n m(n,m<=1000)
接下来n行每行m个正整数
0表示该位置可以经过 1表示该位置不能经过
最左上角的点坐标为(1,1)

Output

一个正整数即答案

Sample 1

Input

3 3
0 1 0
0 0 0
0 0 0

Output

3

Limitation

1s, 128Mb for each test case.

Hint

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original