← 返回题目列表

AtCoder · agc053_c

C. 随机卡牌游戏

中文机器翻译题面 查看原题

分数: 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