阿Q要回家，已知阿Q在 左上角 (1,1) 位置，家在 右下角 (3,3)坐标处。阿Q走上一个格子 (i,j)会花费一定的体力 $a_{i,j}$，而且阿Q只会往家的方向走，也就是只能往下，或者往右走。阿Q想知道他回到家需要花费的最少体力是多少。

3
0 3 4
6 2 5
5 4 3

上面样例：最少花费体力为：3 + 2 + 4 + 3 = 12。

输入格式

第一行输入一个整数 n(1≤n≤1000)。

接下来n行，每行 n 个整数 $a_i(1 \le a_i \le 100)$，表示读入的序列元素。

输出格式

输出最后答案对于 100007 取模的结果。

样例输入

3
0 3 4
6 2 5
5 4 3

样例输出

12