题目描述

有 $2N$ 张卡牌，每张卡牌上分别标有 $1$ 到 $2N$ 的编号。我们来考虑使用这些卡牌进行如下游戏。

首先，庄家会将所有卡牌随机分成两堆，每堆各有 $N$ 张卡牌。同时，庄家还会随机决定每堆卡牌的顺序。接下来，玩家会不断重复以下操作，直到其中一堆卡牌被取空为止，最终操作的总次数即为本游戏的得分。

• 选择一个正整数 $k$，比较一堆中从上往下第 $k$ 张卡牌与另一堆中从上往下第 $k$ 张卡牌的编号（注意，$k$ 不能超过任意一堆的剩余卡牌数）。然后，将编号较小的那张卡牌从其所在的堆中移除。

假设玩家是“作弊者”，也就是说，玩家始终能够知道两堆中所有卡牌的编号。请你求出当玩家以最优策略使得得分最小化时，最终得分的期望值。答案对 $10^9+7$ 取模（见提示）。

输入格式

输入通过标准输入给出。

$N$

输出格式

请输出答案。

样例 1

输入

1

输出

1

样例 2

输入

3

输出

486111118

说明/提示

注记

• 所求的期望值是一个有理数。设其为分数 $\frac{y}{x}$（$x$ 和 $y$ 是互质的正整数），则 $x$ 与 $P=10^9+7$ 互质。请输出满足 $xz \equiv y \pmod{P}$ 的唯一整数 $z$，其中 $0 \leq z < P$。

约束条件

• $1 \leq N \leq 10^6$。

由 ChatGPT 4.1 翻译