[AGC032F] One Third
题意翻译
有一个圆比萨要切成 $n$ 块,每刀是一条半径。由于你技术不好,你只会独立均匀地随机 $n$ 个角度来切。切完之后你会取出圆上相邻的若干块吃掉。
设这个比萨的面积为 $1$ ,你要找到面积最接近 $\frac{1}{3}$ 的这若干块,即设你取出的面积为 $x$,你想要找到 $\lvert x-\frac{1}{3} \rvert$ 最小的一种方案。求这个最小值的期望,对 $10^9+7$ 取模。
$2\le n\le 10^6$
题目描述
[problemUrl]: https://atcoder.jp/contests/agc032/tasks/agc032_f
円形のピザがあります。 すぬけ君は、なるべくこのピザの $ 1/3 $ に近い分量食べたいです。
すぬけ君は、以下のようにピザを切って食べることにしました。
まず、すぬけ君はピザに $ N $ 回ナイフを入れて $ N $ 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。
次に、すぬけ君は一個以上のいくつかの **連続する** ピースをなるべく合計量が $ 1/3 $ に近くなるように選んで食べます。 (合計量を $ x $ とすると、 $ |x\ -\ 1/3| $ が最小となるように連続するピースを選びます。)
このとき、 $ |x\ -\ 1/3| $ の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod $ 10^9\ +\ 7 $ で出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $
输出格式
$ |x\ -\ 1/3| $ の期待値を注記で述べるように mod $ 10^9\ +\ 7 $ で出力せよ。
输入输出样例
输入样例 #1
2
输出样例 #1
138888890
输入样例 #2
3
输出样例 #2
179012347
输入样例 #3
10
输出样例 #3
954859137
输入样例 #4
1000000
输出样例 #4
44679646
说明
### 注記
有理数を出力する際は、まずその有理数を分数 $ \frac{y}{x} $ として表してください。ここで、$ x,\ y $ は整数であり、$ x $ は $ 10^9\ +\ 7 $ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、$ xz\ \equiv\ y\ \pmod{10^9\ +\ 7} $ を満たすような $ 0 $ 以上 $ 10^9\ +\ 6 $ 以下の唯一の整数 $ z $ を出力してください。
### 制約
- $ 2\ \leq\ N\ \leq\ 10^6 $
### Sample Explanation 1
期待値は $ \frac{5}{36} $ です。
### Sample Explanation 2
期待値は $ \frac{11}{162} $ です。