Problem1017--最优对称路径

1017: 最优对称路径

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

给一个 n 行 n 列的网格,每个格子里有一个 1 到 9 的数字。你需要从左上角走到右下角,其中每一步只能 往上、下、左、右四个方向之一走到相邻格子,不能斜着走,也不能走出网格,但可以重复经过一个格子。为 了美观,你经过的路径还必须关于“左下-右上”这条对角线对称。下图是一个 6x6网格上的对称路径。 

你的任务是统计所有合法路径中,数字之和最小的路径有多少条。


Input

输入最多包含 25组测试数据。每组数据第一行为一个整数 n(2<=n<=100)。以下 n 行每行包含 n 个 1 到 9 的数字,表示输入网格。输入结束标志为 n=0。 

Output

对于每组数据,输出合法路径中,数字之和最小的路径条数除以 1,000,000,009 的余数。 

Sample Input Copy

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

Sample Output Copy

2
3