Time limit: 1 second

Memory limit: 256 megabytes

题目描述

感觉不如以撒。。。原神

以撒在笛卡尔坐标系上玩的时候，不小心使用了 "锯齿剪"，所以他现在失去了头。由于怪物就在他身边，他现在很害怕，想赶紧远离怪物。

但因为他没有头，所以他失去了方向感，因此他只能够从上下左右四个方向随机选取一个方向进行逃窜。此刻房间中唯一的怪物所在的坐标是 $(0, 0)$，以撒也在点 $(0, 0)$ 处。

由于怪物石化了，需要 $n$ 个时刻才能追过来。

每个时刻以撒只能够从上下左右四个方向随机选取一个方向跑出一个单位长度。规定上为 $y$ 轴正方向，下为 $y$ 轴负方向，左为 $x$ 轴负方向，右为 $x$ 轴正方向。

在 $n$ 个时刻之后，记以撒位于坐标 $(x, y)$ 处，那么以撒与原点 $(0, 0)$ 间的欧式距离 $S = \sqrt{x ^ 2 + y ^ 2}$。

现在，请问两者欧氏距离的平方 $S^2$ 的期望 $E(S ^ 2)$ 是多少？

期望： 这里的期望指的是数学期望，是试验中每次可能结果的概率乘以其结果的总和。

例如，在走了 $n$ 步后，以撒可能有 $4^n$ 种走法，其中每种走法的可能落在的位置分别为：$(x_1, y_1)$，$(x_2, y_2)$, $\ldots$, $(x_{4^n} ，y_{4^n})$。而你需要计算的是：$\displaystyle \frac{(x_1^2+y_1^2)+(x_2^2+y_2^2)+\ldots+(x_{4^n}^2+y_{4^n}^2)}{4^n}$。

输入

输入就一行 $n$。

输出

你需要输出以撒和原点 $(0,0)$ 间的欧氏距离的平方的期望 $E(S^2)$。

答案可能存在小数，为了方便我们只需输出整数部分即可。

限制

$1 \le n \le 2000$

1

1

样例解释

时间刚过一秒，如果以撒向左边跑，那么坐标为 $(-1,0)$，右边跑坐标为 $(1,0)$，向上跑坐标为 $(0,1)$，向下跑坐标为 $(0,-1)$。

可以发现，无论往哪个方向跑，其距离原点的欧式距离的平方 $S^2$ 都是 $1$，那么 $S^2$ 的期望肯定就是 $1$。