题目描述

你计划在葡萄牙北部的佩内达-热雷什国家公园进行徒步旅行。公园的名字来自其中两座最高峰：佩内达峰（$1340$ 米）和热雷什峰（$1545$ 米）。

在本题中，公园被建模为一个无限整数平面。每个整数坐标位置 $(x,y)$ 都有一个确定的海拔高度。

海拔由一个 $n\times n$ 的矩阵 $h$ 周期性地铺满整个平面。具体地，对于任意整数 $a,b$ 以及 $0\le x,y<n$，位置

$$(x+an,y+bn)$$

的海拔为 $h[x][y]$。

当你位于 $(x,y)$ 时，可以移动到四个相邻位置之一：

$$(x,y+1),\quad(x+1,y),\quad(x,y-1),\quad(x-1,y).$$

若当前位置和目标位置的海拔分别为 $\operatorname{alt}_1$ 和 $\operatorname{alt}_2$，则这次移动所需的时间为：

$$1+\left|\operatorname{alt}_1-\operatorname{alt}_2\right|.$$

你的初始位置为 $(0,0)$。

请计算在 $10^{20}$ 秒内能够到达的不同整数位置数量。

当你的答案相对误差小于 $10^{-6}$ 时，将被认为正确。也就是说，若你的输出为 $x$，标准答案为 $y$，则应满足：

$$\frac{|x-y|}{|y|}<10^{-6}.$$

输入格式

第一行包含一个整数 $n$：

$$2\le n\le 20.$$

接下来 $n$ 行，每行包含 $n$ 个整数。

第 $i+1$ 行的第 $j+1$ 个数为 $h[i][j]$，其中：

$$0\le h[i][j]\le 1545.$$

输出格式

输出在 $10^{20}$ 秒内能够到达的不同整数位置数量。

答案相对误差小于 $10^{-6}$ 即可。

样例 1

输入

2
3 3
3 3

输出

2e+40

说明

所有位置的海拔均为 $3$，因此任意一步移动都恰好耗时 $1$ 秒。

位置 $(x,y)$ 在 $10^{20}$ 秒内可达，当且仅当：

$$|x|+|y|\le 10^{20}.$$

可达位置的精确数量为：

20000000000000000000200000000000000000001

它可以在相对误差要求内近似为 $2\times 10^{40}$。

样例 2

输入

3
0 0 0
0 1545 0
0 0 0

输出

2e+40

说明

所有满足 $x-1$ 和 $y-1$ 都能被 $3$ 整除的位置 $(x,y)$ 海拔为 $1545$，其余位置海拔为 $0$。

例如，从 $(4,10)$ 移动到 $(4,9)$ 需要 $1546$ 秒，而从 $(3,2)$ 移动到 $(4,2)$ 只需 $1$ 秒。

在 $2$ 秒内可达的位置为所有满足 $|x|+|y|\le2$ 的位置，但不包含峰顶 $(1,1)$。

在 $10^{20}$ 秒内可达位置的精确数量为：

19999999999999999931533333333333333863441

它同样可以在误差范围内近似为 $2\times10^{40}$。

样例 3

输入

4
0 1 2 3
5 6 7 4
10 11 8 9
15 12 13 14

输出

1.524886878e+39