题目描述

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

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

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

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

输入格式

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

$N$

输出格式

答えを出力せよ。

题目大意

给定 $2n$ 张卡牌，顺次编号为 $1$ 至 $2n$。考虑如下的游戏：

首先，庄家随机地将卡牌分成两堆，每堆 $n$ 张。每堆内牌的顺序也是随机的。随后，玩家会重复以下操作直到其中一堆为空：
选择一个正整数 $k$，比较两堆中从上到下第 $k$ 张卡牌（$k$ 必须不大于牌堆的大小）。随后，移除两张牌中编号更小的牌。
操作次数即为玩家的得分。

假设玩家是一名作弊者，能看到两堆牌中每张牌的编号。玩家将采用最优策略最小化得分，请输出玩家的期望得分在模 $10^9 + 7$ 意义下的值。

本题中的期望得分是一个分数。假设我们将答案表示为最简分数 $\frac xy$，你需要输出的值即为满足 $yz \equiv x\pmod {10^9 + 7}$ 的值 $z$。

$n\le 10^6$。

1

1

3

486111118

提示

注記

• 求める期待値は有理数となります。期待値を分数 $\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$