该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
Euphemia到一个NN的药草田里采药，她从左上角的格子田（第一行，第一列）出发，要到达右下角（第N行，第N列）的格子田，每次她可以走到与当前格子有边相邻的格子去，但她不会走已经走过的格子，而且出于对美的要求，她走过的路径是关于 左下-右上 对角线对称的。由于地势不同，在每个格子田采药都会有一个疲劳度Tij，Euphemia想知道：有多少条合法路径，可以使得她采药的疲劳度最小。
【输入格式】：
多组数据。
每组数据第一行一个整数N，接下来N行，每行N个非零数字（1,2,3...9中一个），表示格子田的疲劳度。
当N=0，输入结束。
【输出格式】：
对于每组数据，输出一个整数表示答案，答案%1000000009。
【样例输入】：
2
1 1
1 1
3
1 1 1
1 1 1
2 1 1
0
【样例输出】：
2
3
【数据范围与限制】：
对于20%的数据满足N<=5。
对于另外20%的数据满足N<=40。
对于100%的数据满足N<=100,不超过50组数据。
*