C - Random Card Game 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 900 点

問題文

2N 枚のカードがあり、それぞれには 1 から 2N までの番号が付いています。 このカードを用いて行う、次のゲームを考えます。

まず、ディーラーはそれぞれの山が N 枚のカードからなるように、カードを 2 つの山にランダムに分けます。 このとき、ディーラーは各山におけるカードの順序もランダムに定めます。 その後プレイヤーは、一方の山が空になるまで次の操作を繰り返し行い、最終的な操作回数がこのゲームのスコアとなります。

  • ある正の整数 k を選び、一方の山の上から k 枚目のカードと、もう一方の山の上から k 枚目のカードを比較する。（ただし、k は各山のカード枚数を超えてはいけない。）そして、番号が小さい方のカードをそのカードを含む山から取り除く。

このゲームを チーター がプレイするとします。 つまり、各山の各カードの番号を常に把握できるプレイヤーがプレイするとします。 このプレイヤーがスコアを最小化するよう最適にプレイしたときの、スコアの期待値を \bmod 10^9+7 で求めてください（注記参照）。

注記

  • 求める期待値は有理数となります。期待値を分数 \frac{y}{x}（x と y は互いに素な正の整数）で表したとき、x は P=10^9+7 と互いに素になるので、 xz \equiv y \pmod P なる 0 以上 P-1 以下の唯一の整数 z を出力してください。

制約

  • 1 \leq N \leq 10^6

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

1

出力例 1

1

入力例 2

3

出力例 2

486111118

Score : 900 points

Problem Statement

We have 2N cards, with ID numbers from 1 through 2N. Consider the following game using them.

First, the dealer randomly split the cards into two piles of N cards each. Here, the dealer also randomly chooses the order of cards in each pile. Then, the player repeatedly does the operation below until one pile becomes empty, and the number of operations done will be the score.

  • Choose a positive integer k and compare the k-th cards from the top in the two piles. (k should not exceed the number of each pile.) Then, remove the card with the smaller ID number from the pile that contains it.

Assume that a cheater plays this game. That is, assume that the player can always see the ID numbers of all cards in both piles. Find the expected value of the score when the player plays optimally to minimize it, modulo (10^9 + 7) (see Notes).

Notes

  • The expected value in question will be a rational number. If we express it as a fractional number \frac{y}{x} where x and y are coprime positive integers, x will be coprime with P=10^9+7, so print the only integer z between 0 and P-1 (inclusive) such that xz \equiv y \pmod P.

Constraints

  • 1 \leq N \leq 10^6

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

1

Sample Output 1

1

Sample Input 2

3

Sample Output 2

486111118