QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 1024 MB Total points: 100

# 5406. 随机游走

Statistics

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

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

每一次,小 W 会选择一个等概率均匀随机的向量 $(x,y)$,使得 $x,y \in \mathbb R$,$|x|+|y|\le 1$。之后他会恰好沿着向量移动一次,即若当前坐标为 $(A, B)$,小 W 会移动到 $(A+x, B+y)$。

小 W 总共会进行 $n$ 次上述的游走操作。在结束所有 $n$ 次操作后,小 W 会结束这次游走。

小 W 对游走的结果很感兴趣,现在他想要知道,在结束游走时,他离 $y$ 轴距离的期望到底是多少。也就是,设结束时的坐标为 $(A, B)$,你需要求出 $|A|$ 的期望大小。

由于答案的表达式可能非常的复杂,你只需要输出答案对质数 $p=1\,000\,000\,007$ $(10^9+7)$ 取模的结果即可。

输入格式

一行一个正整数 $n$,表示小 W 进行的操作次数。

输出格式

一行一个正整数,表示答案对质数 $p=1\,000\,000\,007$ $(10^9+7)$ 取模的结果。

可以证明对于所有输入,答案总可以表示成 $\frac 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$。