问题描述

我们有 $N$ 盏灯，编号为 $1$ 到 $N$，以及 $N$ 个按钮，编号为 $1$ 到 $N$。最初，灯 $1,2,\\cdots, A$ 是开着的，其他灯是关着的。

Snuke 和 Ringo 将进行以下游戏。

• 首先，Ringo 生成一个排列 $(p_1,p_2,\\cdots,p_N)$，它是 $(1,2,\\cdots,N)$ 的所有 $N!$ 种可能排列之一，并且每种排列被选中的概率相等，而不会告知给 Snuke。

• 然后，Snuke 可以任意次数地执行以下操作：

  • 选择一盏此刻是开着的灯。（如果没有这样的灯，则无法执行操作。）设选中的灯是第 $i$ 盏灯。按下按钮 $i$，它会改变灯 $p_i$ 的状态。也就是说，如果灯 $p_i$ 是开着的，按下按钮后它将关闭；如果灯 $p_i$ 是关着的，按下按钮后它将打开。

在任何时刻，Snuke 都知道哪些灯是开着的。当所有灯都是开着的时候，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