描述

有一个 $n \times n$ 的游戏棋盘，每个方格内填充着一个非负整数。游戏的目标是从棋盘的左上角出发，沿着合法的路径移动到右下角。每个方格中的整数表示从该位置出发时必须移动的步长。如果移动步长会导致超出棋盘边界，则该方向的移动是被禁止的。所有移动只能向右或向下进行。注意，数字 $0$ 表示死路，会阻止进一步的移动。

以图$1$所示的 $4 \times 4$ 棋盘为例，实心圆标记起点，虚线圆标记终点。图$2$展示了从起点到终点的三条路径，并移除了每条路径中无关的数字。

|

输入

输入包含最多 $30$ 个棋盘的数据，最后一行以单独的 $-1$ 结束。每个棋盘的数据以一行正整数 $n$ 开始，$4 \leq n \leq 34$，表示棋盘的行数。接下来是 $n$ 行数据，每行包含 $n$ 个数字 $0$-$9$，数字之间没有空格。

输出

对于每个棋盘，输出一行一个整数，表示从左上角到右下角的路径数量。任何棋盘的路径数都少于 $2^{63}$。

输入数据 $1$

4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1

输出数据 $1$

3
0
7

提示

暴力枚举所有路径的方法可能会超出时间限制。在$Java$中可以使用$long$类型，在$C/C++$中可以使用$long$ $long$类型来存储$64$位整数。

来源

2005年美国中西部地区竞赛