You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 有一个 $n$ 个点的完全无向图，也就是任意两个点之间都有一条无向边相连，也就是一共有 $\frac{n(n-1)}{2}$ 条边。

首先 小 Z 给这些边加上权值，权值都是 $[1,\frac{n(n-1)}{2}]$ 里的正整数，且两两不同。

换句话说，就是所有边的权值合起来是一个 $1,\dots,\frac{n(n-1)}{2}$ 的排列。

然后 小 Y 会依次看过每一个点，对于每一个点与其相连的 $n-1$ 条边，小 Y 会把权值最大的那个边点亮。

可以发现这个过程中，有些边可能会被点亮很多次，有的边可能一次都没有被点亮。

接着 小 Z 会删掉一次都没有被点亮过的边，那么剩下的边会把整个图分成若干个连通块。

现在 小 Y 想问你，假设 小 Z 以完全随机的方式给所有边加上权值，图被分成 $k$ 个连通块的概率是多少？

输入格式

从 light.in 文件读入数据。

第一行一个正整数 $t$ ，代表数据组数。

接下来 $t$ 行，每行两个数字 $n,k$ 代表一个询问。

输出格式

输出到 light.out 文件。

输出 $t$ 行，每行一个正整数，表示答案对 $10^9+7$ 取模的值。

样例

10
2 1
3 1
4 1
4 2
5 1
11 3
35 1
36 11
45 8
343199 76201

1
1
600000005
400000003
571428576
508216246
489962980
159589188
666252456
820710152

数据范围

对于所有数据，$1\le t\le 10, 1\le n\le 500000, 1\le k\le n$。