题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的灯，以及 $N$ 个编号为 $1$ 到 $N$ 的按钮。一开始，编号为 $1,2,\cdots,A$ 的灯是点亮的，其余的灯是熄灭的。

Snuke 和 Ringo 决定进行如下游戏：

• 首先，Ringo 生成一个 $1$ 到 $N$ 的排列 $(p_1,p_2,\cdots,p_N)$。该排列从 $N!$ 种可能中等概率随机选取。Snuke 并不知道这个排列。

• 接下来，Snuke 可以任意多次进行如下操作：

  • 从当前点亮的灯中任选一个（如果没有点亮的灯则无法操作）。设选中的灯编号为 $i$，然后按下按钮 $i$。这样，编号为 $p_i$ 的灯的状态会被反转（如果原来点亮则变为熄灭，原来熄灭则变为点亮）。

Snuke 始终可以知道哪些灯是点亮的。Snuke 的胜利条件是让所有灯都点亮。如果确定无法达成目标，Snuke 就认输。当 Snuke 采取最优策略时，他的胜率是多少？

设 Snuke 的胜率为 $w$，则 $w\times N!$ 一定是整数。请输出 $w\times N!$ 对 $10^9+7$ 取模的结果。

输入格式

输入从标准输入读入，格式如下：

$N$ $A$

输出格式

设 Snuke 的胜率为 $w$，请输出 $w\times N!$ 对 $10^9+7$ 取模的结果。

样例 1

输入

3 1

输出

2

样例 2

输入

3 2

输出

3

样例 3

输入

8 4

输出

16776

样例 4

输入

9999999 4999

输出

90395416

说明/提示

限制

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

样例解释 1

Snuke 首先按下按钮 $1$。如果灯 $1$ 被熄灭，则 Snuke 失败。否则，按下新点亮的灯对应的按钮。如果剩下的灯被点亮，则 Snuke 获胜。反之，如果灯 $1$ 被熄灭，则 Snuke 失败。这个游戏的胜率是 $1/3$，所以输出 $(1/3)\times 3! = 2$。

由 ChatGPT 4.1 翻译