有一种从数组中删除元素的经典方法：将要删除的元素与数组的最后一个元素交换数值，然后删除最后一个元素。不幸的是，这种方法并不总是能保持数组中元素的顺序。你的任务是计算进行 $k$ 次删除操作的序列数量，使得最初升序排序的数组在操作后仍然保持有序。

给你一个长度为 $n$ 的数组 $a$，初始时按升序填入 $1$ 到 $n$ 的数字，即 $a_i = i$；以及一个长度为 $k$ 的数组 $b$，其元素是 $1$ 到 $n$ 之间两两不同的数字。

共进行 $k$ 步操作，在第 $j$ 步中会发生以下过程：在 $1$ 到 $n - j + 1$ 中选择一个下标 $i$ 使得 $a_i = b_j$，然后交换 $a_i$ 和 $a_{n - j + 1}$（如果 $i = n - j + 1$，则什么都不做）。接着，将此时数组的最后一个元素（其下标为 $n - j + 1$）从数组中删除。

如果进行 $k$ 步操作后，数组 $[a_1, a_2, \dots, a_{n - k}]$ 是严格单调递增的，则称数组 $[b_1, b_2, \dots, b_k]$ 是好的。

给定数字 $n$ 和 $k$，求好数组 $[b_1, b_2, \dots, b_k]$ 的数量。由于答案可能很大，请输出答案模 $10^9 + 7$ 的余数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来的 $t$ 行提供测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$)。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 好数组 $b$ 的数量模 $10^9 + 7$ 的结果。

样例

输入样例 1

5
1 0
1 1
2 2
3 1
4 2

输出样例 1

1
1
2
2
7

说明

让我们分析样例中的第四个测试用例。在此用例中，$n = 3$ 且 $k = 1$。初始时，$a = [1, 2, 3]$。让我们看看对于所有可能的数组 $b$，在第一步之后 $a$ 是如何变化的。

• $b = [1]$：然后 $a$ 的变化如下：$[1, 2, 3] \to [3, 2, 1] \to [3, 2]$。数组 $[3, 2]$ 不是递增的。
• $b = [2]$：然后 $a$ 的变化如下：$[1, 2, 3] \to [1, 3, 2] \to [1, 3]$。数组 $[1, 3]$ 是递增的。
• $b = [3]$：然后 $a$ 的变化如下：$[1, 2, 3] \to [1, 2, 3] \to [1, 2]$。数组 $[1, 2]$ 是递增的。

我们发现有两个好数组 $b = [2]$ 和 $b = [3]$，因此样例中第四个测试用例的答案是 2。