406558: GYM102439 L The only winner

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. The only winnertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Andrew decided to give a gift to one of his $$$n$$$ guests. In order to choose the lucky one, Andrew decided to arrange a lottery. To do this, he took $$$2n$$$ cards with numbers from $$$1$$$ to $$$2n$$$, mixed them and gave two cards to each guest. The gift will be given to the guest, whose sum of the numbers on the cards is the maximum. However, after Andrew handed out the cards, he realized that there could be several winners. He asks you to calculate the probability that he will not have to look for additional gifts.

Input

The only line contains one integer $$$n$$$. $$$$$$1 \leq n \leq 10^5$$$$$$

Output

Let the answer to the problem be an irreducible fraction $$$\frac{P}{Q}$$$.

Output $$$P \times Q^{-1}$$$ modulo $$$10^9+7$$$ as the answer. It is guaranteed that $$$Q$$$ is not divisible by $$$10^9+7$$$.

ExampleInput
2
Output
666666672

加入题单

上一题 下一题 算法标签: