请注意不同寻常的内存限制。

设 $f(n, k, x)$（其中 $n > k > x \ge 1$）表示长度为 $n$ 的整数数组的数量，该数组满足：包含 $1$ 到 $x$ 的整数各恰好一次，包含 $x+1$ 到 $k$ 的整数各至少两次，且不包含任何其他整数。例如，$f(7, 4, 2) = 840$，因为放置 $1$ 有 $7$ 种方式，放置 $2$ 有 $6$ 种方式，在剩下的 $5$ 个位置中放置 $3$ 和 $4$ 使得 $3$ 和 $4$ 都至少出现两次有 $20$ 种方式。

给定整数 $n$ 和 $k$。求 $f(n, k, 1), f(n, k, 2), \dots, f(n, k, k - 1)$ 中最大的 $9$ 个值，并输出它们的和对 $10^9 + 7$ 取模的结果。

输入格式

输入包含一个或多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^6$)。 每个测试用例仅一行，包含两个整数 $n$ 和 $k$ ($10^4 \ge n > k \ge 10$)。

输出格式

对于每个测试用例，输出一个整数：最大的 $9$ 个值的和对 $10^9 + 7$ 取模的结果。

样例

输入格式 1

3
17 12
88 24
6949 4513

输出格式 1

567627977
225618886
360966919

说明

在第一个测试用例中，$f(17, 12, 1) = f(17, 12, 2) = \dots = f(17, 12, 6) = 0$，因此答案仅为剩余非零值的和。