问题描述

具体描述见教材p146：在一个n*n个方格的游戏板中，每个方格中有一个非负整数。游戏的目标是从游戏板的左上角沿任何合法路径移动到右下角。任何一个方格内的数字规定了离开本方格的一步必须移动的方式数。如果移动的一步超出来游戏板， 则这个方向的移动是禁止的。每一步移动只能是向下或向右的。如下图，这时正体字表示出发位置，红色斜体字表示目的位置。后面显示了从出发位置到目的位置的三条路径，其中隐去了与每条路径无关的数字。

格式

输入

输入文件含有n+1行，第1行是游戏板的行数n(4<=n<=34)， 接下来是n个数据行， 每行含有n个0~9的数字，中间没有空格。

输出

在1行中输出从左上角到右下角的路径数（注：输出的路径使用长整型数据类型）。

样例

4
2331
1213
1231
3110

3

4
3332
1213
1232
2120

0

5
11111
11111
11111
11111
11111

70

限制

1s, 64MB.