LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。
整个 HDU 校园呈方形布局，可划分为 n*n 个小方格，代表各个区域。
例如 LL 居住的 18 号宿舍位于校园的西北角，即方格 (1,1) 代表的地方，而机房所在的第三实验楼处于东南端的 (n,n)。
因有多条路线可以选择，LL 希望每次的散步路线都不一样。
另外，他考虑从 A 区域到 B 区域仅当存在一条从 B 到机房的路线比任何一条从A到机房的路线更近，否则可能永远都到不了机房了。
现在他想知道的是，所有满足要求的路线一共有多少条。

第一行一个整数 n (2≤n≤50)；
接下来 n 行每行有 n 个数，代表经过每个区域所花的时间 t (0＜t≤50)。由于寝室与机房均在三楼，故起点与终点也得费时。

针对每组测试数据，输出总的路线数，小于 $2^63$。