QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 1024 MB Total points: 100
[+1]

# 5406. 随机游走

Statistics

小 W 是随机大师,他特别喜欢随机化算法。

这一天,小 W 站在原点 (0,0) 开始了他的随机游走。

每一次,小 W 会选择一个等概率均匀随机的向量 (x,y),使得 x,yR|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