One Third

AtCoder

IDagc032_f

Time2000ms

Memory256MB

Difficulty—

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. ## Constraints * $2 \leq N \leq 10^6$ ## Input Input is given from Standard Input in the following format: $N$ [samples] ## 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}$.

Samples

Input #1

Output #1

138888890

The expected value is $\frac{5}{36}$.

Input #2

Output #2

179012347

The expected value is $\frac{11}{162}$.

Input #3

Output #3

954859137

Input #4

Output #4

44679646

API Response (JSON)

{
  "problem": {
    "name": "One Third",
    "description": {
      "content": "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$",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc032_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a round pizza. Snuke wants to eat one third of it, or something as close as possible to that.\nHe decides to cut this pizza as follows.\nFirst, he divides the pizza into $N$ pieces by making $N$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments