← 返回题目列表

AtCoder · agc053_f

F. 超能力者

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

分数: 2400 点

问题陈述

2N+1 玩家将玩一个名为“多数投票”的游戏。每个玩家对给出的两个选项之一进行投票,选择最终得票数较多的选项的玩家将获胜。投票具体进展如下:

  1. 如果所有人都已投票,则投票结束。否则,请继续步骤 2。
  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