路径计数

题目描述

有一个$n\times n$的网格，有些格子是可以通行的，有些格子是障碍。

一开始你在左上角的位置，你可以每一步往下或者往右走，问有多少种走到右下角的方案。

由于答案很大，输出对$10^9+7$取模的结果。

输入格式

第一行一个正整数$n$。

接下来$n$行，每行$n$个正整数，$1$表示可以通行，$0$表示不能通行。

输出格式

一个整数，表示答案。

样例输入

3
1 1 1
1 0 1
1 1 1

样例输出

2

数据范围

对于$100\%$的数据，保证$2\leq n\leq 100$，左上角右下角都是可以通行的。