题目描述

从数组中删除一个元素有一种经典方法：把要删除的元素和数组最后一个元素交换，然后删除最后一个元素。可惜，这种删除方法不一定能保持数组有序。

初始数组 $a$ 长度为 $n$，并且

另有一个长度为 $k$ 的数组 $b$，其中元素是 $1$ 到 $n$ 之间两两不同的数。

接下来进行 $k$ 步操作。第 $j$ 步时，找到当前数组中值等于 $b_j$ 的位置 $i$，将 $a_i$ 与当前最后一个元素交换，然后删除最后一个元素。

如果执行完这 $k$ 步后，剩余数组严格递增，则称数组 $b$ 是好的。

给定 $n$ 和 $k$，请你求好的数组 $b$ 有多少个。答案对 $10^9+7$ 取模。

输入格式

第一行输入整数 $t$，表示测试数据组数。

接下来 $t$ 行，每行两个整数 $n,k$。

所有测试数据中 $n$ 的总和不超过 $5\cdot 10^5$。

输出格式

对每组数据输出一个整数，表示好的数组数量，结果对 $10^9+7$ 取模。

样例

5
1 0
1 1
2 2
3 1
4 2

1
1
2
2
7