← 返回题目列表

AtCoder · agc045_d

D. 灯和按钮

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

分数: 1200 点

问题陈述

我们有 N 灯编号 1 to N,和 N 按钮编号 1 to N。 最初,灯 1, 2, \cdots, A 亮起,其他灯熄灭。

Snuke 和 Ringo 将玩以下游戏。

  • 首先,Ringo 生成一个排列 (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N)。 排列是从所有排列中选择的 N! 可能的排列具有相同的概率,无需通知 Snuke。

  • 然后,Snuke 执行以下操作任意次数:

    • 选择当前打开的灯。 (如果没有该灯则无法进行操作。) 让灯 i 是所选的灯。 按下按钮 i,切换 Lamp 的状态 p_i。也就是灯 p_i 打开则关闭,反之亦然。

每时每刻,Snuke 都知道哪些灯亮着。 如果所有的灯都亮了,斯努克就会获胜,而当他无法获胜时,他就会投降。 当 Snuke 发挥最佳时获胜的概率是多少?

让 w 是获胜的概率。然后, w \times N! 将是一个整数。 计算 w \times N! 模数 (10^9+7).

约束

  • 2 \leq N \leq 10^7
  • 1 \leq A \leq \min(N-1,5000)

输入

输入由标准输入按以下格式给出:

N A

输出

打印 w \times N! 模数 (10^9+7),其中 w 是 Snuke 获胜的概率。


示例输入 1

3 1

示例输出 1

2

首先,Snuke 将按下按钮 1。 如果灯 1 关闭,他输了。 否则,他将按下他现在可以按下的按钮。 如果剩下的灯亮了,他就赢了;如果剩下的灯亮了,他就赢了。如果灯 1 关闭,他输了。 这场比赛获胜的概率是 1/3,所以我们应该打印 (1/3)\times 3!=2.


示例输入 2

3 2

示例输出 2

3

示例输入 3

8 4

示例输出 3

16776

示例输入 4

9999999 4999

示例输出 4

90395416