分数: 900 点
问题陈述
我们有 2N 卡,其 ID 号来自 1 通过 2N。 考虑使用它们的以下游戏。
首先,庄家将牌随机分成两堆 每张 N 卡。 在这里,庄家还随机选择每堆牌的顺序。 然后,玩家重复进行下面的操作,直到一堆空了,完成的操作次数就是得分。
- 选择一个正整数 k 并比较 k两堆中从顶部算起的第张牌。 (k 不应超过每堆的数量。)然后,从包含 ID 号的卡片堆中取出 ID 号较小的卡片。
假设 骗子 玩这个游戏。 也就是说,假设玩家总是可以看到两堆中所有牌的 ID 号。 求当玩家以最佳状态进行游戏时得分的期望值,以最小化它,取模 (10^9 + 7) (见注释)。
注释
- 所讨论的期望值将是一个有理数。如果我们将其表示为分数 \frac{y}{x} 其中 x 和 y 是互质正整数, x 将与 P=10^9+7,所以打印唯一的整数 z 之间 0 和 P-1 (含)使得 xz \equiv y \pmod P.
约束
- 1 \leq N \leq 10^6
输入
输入由标准输入按以下格式给出:
N
输出
打印答案。
示例输入 1
1
示例输出 1
1
示例输入 2
3
示例输出 2
486111118