分数: 2400 点
问题陈述
2N+1 玩家将玩一个名为“多数投票”的游戏。每个玩家对给出的两个选项之一进行投票,选择最终得票数较多的选项的玩家将获胜。投票具体进展如下:
- 如果所有人都已投票,则投票结束。否则,请继续步骤 2。
- 从未投票的玩家中随机选择一名玩家,并进行投票。然后,返回步骤 1。
K 的玩家是ESPers,他们在投票时可以知道每个选项的票数。 因此,玩家选择施放选项如下:
- 作为 ESPer 的玩家选择当前得票数较多的选项。如果两个选项的票数相同,则他/她随机选择一个选项并投票。
- 非 ESPer 的玩家随机选择一个选项并投票。
X 是游戏玩家,同时也是 ESPer。求 X 获胜的概率,取模 (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 2\times 10^6
- 1 \leq K \leq 2N+1
输入
输入由标准输入按以下格式给出:
N K
输出
打印答案。
示例输入 1
1 1
示例输出 1
916666674
X 有概率获胜 \frac{11}{12}.
示例输入 2
1 2
示例输出 2
958333341
X 有概率获胜 \frac{23}{24}.
示例输入 3
8 5
示例输出 3
582281799
示例输入 4
100 100
示例输出 4
196654831
示例输入 5
2000000 2000000
示例输出 5
768385859