有一个$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$,左上角右下角都是可以通行的。