问题背景

我们称一个大小为 $n$ 的数列 $p_1, p_2, \ldots, p_n$ 是一个排列，当且仅当整数 $1 \sim n$ 在排列 $p$ 中均出现恰好一次。比如：

• $[1, 2, 3, 4]$ 是一个大小为 $4$ 的排列；
• $[5, 3, 2, 4, 1, 6, 7]$ 是一个大小为 $7$ 的排列；
• $[2]$，$[1, 3, 4, 3]$，$[1, 3, 4, 5, 6]$ 都不是排列。

题目描述

给定两个整数 $n$ 和 $k$（$1 \le k \le n \le 1000$），计算有多少个大小为 $n$ 的排列 $p_1, p_2, \ldots, p_n$ 满足如下条件：

最多存在 $k$ 个下标 $i$ 满足 $p_i \neq i$。

由于满足条件的排列数量可能很大，所以你只需要输出满足条件的排列数量模 $10^9+7$ 的结果即可。

输入格式

一行，两个整数 $n$ 和 $k$，以一个空格分隔（$1 \le k \le n \le 1000$）。

输出格式

4 1

1

4 2

7

5 3

31

说明/提示

样例 1 解释

一共有 $1$ 个满足条件的排列：

• $[1,2,3,4]$，共 $0$ 个位置 $p_i \neq i$。

样例 2 解释

一共有 $7$ 个满足条件的排列：

• $[1,2,3,4]$，共 $0$ 个位置 $p_i \neq i$；
• $[1,2,4,3]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 3,4$；
• $[1,3,2,4]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 2,3$；
• $[1,4,3,2]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 2,4$；
• $[2,1,3,4]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,2$；
• $[3,2,1,4]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,3$；
• $[4,2,3,1]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,4$。

样例 3 解释

一共有 $31$ 个满足条件的排列：

• $[1,2,3,4,5]$，共 $0$ 个位置 $p_i \neq i$；
• $[1,2,3,5,4]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 4,5$；
• $[1,2,4,3,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 3,4$；
• $[1,2,4,5,3]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 3,4,5$；
• $[1,2,5,3,4]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 3,4,5$；
• $[1,2,5,4,3]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 3,5$；
• $[1,3,2,4,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 2,3$；
• $[1,3,4,2,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,3,4$；
• $[1,3,5,4,2]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,3,5$；
• $[1,4,2,3,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,3,4$；
• $[1,4,3,2,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 2,4$；
• $[1,4,3,5,2]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,4,5$；
• $[1,5,2,4,3]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,3,5$；
• $[1,5,3,2,4]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 2,4,5$；
• $[1,5,3,4,2]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 2,5$；
• $[2,1,3,4,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,2$；
• $[2,3,1,4,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,3$；
• $[2,4,3,1,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,4$；
• $[2,5,3,4,1]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,5$；
• $[3,1,2,4,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,3$；
• $[3,2,1,4,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,3$；
• $[3,2,4,1,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,3,4$；
• $[3,2,5,4,1]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,3,5$；
• $[4,1,3,2,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,4$；
• $[4,2,1,3,5]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,3,4$；
• $[4,2,3,1,5]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,4$；
• $[4,2,3,5,1]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,4,5$；
• $[5,1,3,4,2]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,2,5$；
• $[5,2,1,4,3]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,3,5$；
• $[5,2,3,1,4]$，共 $3$ 个位置 $p_i \neq i$，对应的 $i = 1,4,5$；
• $[5,2,3,4,1]$，共 $2$ 个位置 $p_i \neq i$，对应的 $i = 1,5$。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 10; k \le 4$
• 对于 $60\%$ 的数据，$n \le 100; k \le 4$
• 对于 $100\%$ 的数据，$1 \le k \le n \le 1000$