Contest Duration: - (local time) (110 minutes) Back to Home
F - One Third /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけ君は、以下のようにピザを切って食べることにしました。

まず、すぬけ君はピザに N 回ナイフを入れて N 個のピースに分割します。 ナイフを入れると、ピザの中心とピザの周上の点を結ぶ線分に沿ってピザに切れ込みが入ります。 ただし、すぬけ君はピザを切るのがとても下手なので、線分の角度は一様ランダムであり、毎回独立であるものとします。

このとき、 |x - 1/3| の期待値を求めてください。 この値は有理数となることが示せます。これを注記で述べるように mod 10^9 + 7 で出力してください。

### 制約

• 2 \leq N \leq 10^6

### 入力

N


### 出力

|x - 1/3| の期待値を注記で述べるように mod 10^9 + 7 で出力せよ。

### 入力例 1

2


### 出力例 1

138888890


### 入力例 2

3


### 出力例 2

179012347


### 入力例 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