题目描述

一个 $n×n$ 的游戏板是由整数填充的，每格一个非负整数。目标是从左上角以任何合法路径跳到右下角。任何一格中的整数表示跳离该位置的步长。如果步长将推进越出游戏板，那么在那个特定的方向上的跳步是禁止的。所有的跳步必须是向右或向下。请注意，$0$ 是一个死胡同，它阻止任何进一步的进展。 如图 $1$ 中所示的 $4×4$ 板，实圆标识起始位置，虚线圆标识目标位置。图 $2$ 展示了从起点位置到目标位置的三条合法路径，每个路径中都删除了不相关的数字。 你的任务是编写一个程序来确定从左上角到右下角的合法路径的数量。

输入格式

第一行包含一个正整数 $n$，表示该板的行列数。接下来 $n$ 行数据。每行包含 $n$ 个整数，每个整数的范围是 $0 \cdots 9$。

输出格式

唯一的一行包含一个整数，即从左上角到右下角的合法路径数对$10^9+7$取模之后结果。

样例 #1

样例输入 #1

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

样例输出 #1

3

提示

数据规模与约定

• 对于 $100 \%$ 的数据， $4 \le n \le 100$。