[AGC032F] One Third

题目描述

[problemUrl]: https://agc032.contest.atcoder.jp/tasks/agc032_f 円形のピザがあります。 すぬけ君は、なるべくこのピザの $1/3$ に近い分量食べたいです。 すぬけ君は、以下のようにピザを切って食べることにしました。 まず、すぬけ君はピザに $N$ 回ナイフを入れて $N$ 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。 次に、すぬけ君は一個以上のいくつかの **連続する** ピースをなるべく合計量が $1/3$ に近くなるように選んで食べます。 (合計量を $x$ とすると、 $|x\ -\ 1/3|$ が最小となるように連続するピースを選びます。) このとき、 $|x\ -\ 1/3|$ の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod $10^9\ +\ 7$ で出力してください。 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.

输入输出格式

输入格式

Input is given from Standard Input in the following format:  $N$ 

输出格式

Print the expected value of $|x\ -\ 1/3|$ modulo $10^9\ +\ 7$ , as described in Notes.

输入输出样例

输入样例 #1

2

输出样例 #1

138888890

输入样例 #2

3

输出样例 #2

179012347

输入样例 #3

10

输出样例 #3

954859137

输入样例 #4

1000000

输出样例 #4

44679646

输入样例 #5

2

输出样例 #5

138888890

输入样例 #6

3

输出样例 #6

179012347

输入样例 #7

10

输出样例 #7

954859137

输入样例 #8

1000000

输出样例 #8

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$ ### 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$ ### Sample Explanation 1 期待値は $\frac{5}{36}$ です。 ### Sample Explanation 2 期待値は $\frac{11}{162}$ です。 ### Sample Explanation 5 The expected value is $\frac{5}{36}$ . ### Sample Explanation 6 The expected value is $\frac{11}{162}$ .