小 W 是随机大师,他特别喜欢随机化算法。
这一天,小 W 站在原点 (0,0) 开始了他的随机游走。
每一次,小 W 会选择一个等概率均匀随机的向量 (x,y),使得 x,y∈R,|x|+|y|≤1。之后他会恰好沿着向量移动一次,即若当前坐标为 (A,B),小 W 会移动到 (A+x,B+y)。
小 W 总共会进行 n 次上述的游走操作。在结束所有 n 次操作后,小 W 会结束这次游走。
小 W 对游走的结果很感兴趣,现在他想要知道,在结束游走时,他离 y 轴距离的期望到底是多少。也就是,设结束时的坐标为 (A,B),你需要求出 |A| 的期望大小。
由于答案的表达式可能非常的复杂,你只需要输出答案对质数 p=1000000007 (109+7) 取模的结果即可。
输入格式
一行一个正整数 n,表示小 W 进行的操作次数。
输出格式
一行一个正整数,表示答案对质数 p=1000000007 (109+7) 取模的结果。
可以证明对于所有输入,答案总可以表示成 xy (y \not\equiv 0 \pmod p) 的形式,此时你只需要输出 (x\times y^{p-2})\bmod p 的结果即可。
样例数据
样例 1 输入
1
样例 1 输出
333333336
样例 1 解释
对于样例 1,答案等于 \displaystyle\int_0^1 x^2\,\mathrm dx=\frac13。
样例 2 输入
3
样例 2 输出
769047625
样例 2 解释
对于样例 2,答案等于 \frac{239}{420}。
数据范围
测试包 1(5\%):n \le 3;
测试包 2(10\%):n \le 10;
测试包 3(10\%):n \le 30;
测试包 4(15\%):n \le 200;
测试包 5(15\%):n \le 2000;
测试包 6(15\%):n \le 2\times 10^5;
测试包 7(30\%):n \le 5\times 10^6。