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