/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 1800 点
問題文
円形のピザがあります。 すぬけ君は、なるべくこのピザの 1/3 に近い分量食べたいです。
すぬけ君は、以下のようにピザを切って食べることにしました。
まず、すぬけ君はピザに N 回ナイフを入れて N 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。
次に、すぬけ君は一個以上のいくつかの 連続する ピースをなるべく合計量が 1/3 に近くなるように選んで食べます。 (合計量を x とすると、 |x - 1/3| が最小となるように連続するピースを選びます。)
このとき、 |x - 1/3| の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod 10^9 + 7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \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
入力
入力は以下の形式で標準入力から与えられる。
N
出力
|x - 1/3| の期待値を注記で述べるように mod 10^9 + 7 で出力せよ。
入力例 1
2
出力例 1
138888890
期待値は \frac{5}{36} です。
入力例 2
3
出力例 2
179012347
期待値は \frac{11}{162} です。
入力例 3
10
出力例 3
954859137
入力例 4
1000000
出力例 4
44679646
Score : 1800 points
Problem Statement
We have a round pizza. Snuke wants to eat one third of it, or something as close as possible to that.
He decides to cut this pizza as follows.
First, he divides the pizza into N pieces by making N cuts with a knife. The knife can make a cut along the segment connecting the center of the pizza and some point on the circumference of the pizza. However, he is very poor at handling knives, so the cuts are made at uniformly random angles, independent from each other.
Then, he chooses one or more consecutive pieces so that the total is as close as possible to one third of the pizza, and eat them. (Let the total be x of the pizza. He chooses consecutive pieces so that |x - 1/3| is minimized.)
Find the expected value of |x - 1/3|. It can be shown that this value is rational, and we ask you to print it modulo 10^9 + 7, as described in Notes.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- 2 \leq N \leq 10^6
Input
Input is given from Standard Input in the following format:
N
Output
Print the expected value of |x - 1/3| modulo 10^9 + 7, as described in Notes.
Sample Input 1
2
Sample Output 1
138888890
The expected value is \frac{5}{36}.
Sample Input 2
3
Sample Output 2
179012347
The expected value is \frac{11}{162}.
Sample Input 3
10
Sample Output 3
954859137
Sample Input 4
1000000
Sample Output 4
44679646