题目背景

欢喜不问天，风流不问天，温柔不问天，良辰不问天，良缘不问天。

问你不问天。

题目描述

情人节那天 $\color{orange}\texttt{Biadocy}$ 被虐得好惨，尤其是上流的公爵和小孩说什么《和你在一起的每一天，都叫情人节》。于是他找到了一个机会来报复。

现在有 $n$ 对情人编号为 $1\sim n$ 按任意顺序排成一列，$\color{orange}\texttt{Biadocy}$ 对他们执行了下面这段排序的伪代码。

$\color{orange}\texttt{Biadocy}$ 想知道有多少种初始排列满足按照这段伪代码排序后情人们的编号有序。也许这能让他好受一点。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行每行两个整数 $n,k$ 表示情人对数和第一次调用伪代码传入的参数。

输出格式

$T$ 行，每行一个整数，表示答案对 $10^9+7$ 取模的结果。

3
3 1
10 2
1 0

3
25200
1

5
502520 0
502520 1
502520 2
502520 3
502520 4

1
218102685
429650441
770595802
584122358

提示

对于前 $10\%$ 的数据，$T=0$。
对于前 $30\%$ 的数据，$T\leq 10$，$n\leq 7$。
对于另外 $10\%$ 的数据，$k=0$。
对于另外 $10\%$ 的数据，$k=100$。
对于 $100\%$ 的数据，$0\leq T\leq 10^5$，$1\leq n\leq 10^6$，$0\leq k\leq 100$。