时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小Y到一个 \(N×N\) 的药草田里采药，她从左上角的格子田（第一行，第一列）出发，要到达右下角（第 \(N\) 行，第 \(N\) 列）的格子田，每次她可以走到与当前格子有边相邻的格子去，但她不会走已经走过的格子，而且出于对美的要求，她走过的路径是关于 左下-右上 对角线对称的。由于地势不同，在每个格子田采药都会有一个疲劳度 \(T_ij\)，小Y想知道：有多少条合法路径，可以使得她采药的疲劳度最小。

【输入格式】

　　多组数据。
　　每组数据第一行一个整数N，接下来 \(N\) 行，每行 \(N\) 个非零数字（1,2,3...9中一个），表示格子田的疲劳度。
　　当 \(N=0\)，输入结束。

【输出格式】

　　 对于每组数据，输出一个整数表示答案，答案 % 1000000009。

【输入输出样例】

　Input

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

　Output

2
3

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤5\)。
　　对于另外 \(20\%\) 的数据，\(1≤N≤40\)。
　　对于 \(100\%\) 的数据，\(1≤N≤100\)，不超过50组数据。

【来源】

　　Mr.he