Intranets

Apricot Rules LLC is developing a new simplified networking protocol and wants to show off its routing algorithm. In their design, a network consists of $M$ machines numbered from $1$ to $M$, and each pair of machines is connected by a direct link. Each link gets a unique integer priority from $1$ to $M(M-1)/2$, and each machine routes traffic according to those priorities.

Unfortunately, the routing algorithm is too aggressive. It routes all traffic from a machine through the highest priority link connected to it. This may isolate some groups of machines from the others.

Formally, a machine $m$ uses a link $\ell$ if and only if $\ell$ is the highest priority link connected to $m$. A link is active if at least one of the two machines it connects uses it. The original network splits into disjoint intranets. Two machines belong to the same intranet if and only if there is a path between them using only active links.

For example, in the left image above, only the links with priorities $6$ and $5$ are active, which creates two disjoint intranets. In the right example, three links are active, so all $4$ machines form one intranet.

As part of the quality assurance team at Apricot Rules LLC, you are investigating how serious the problem is. Find the probability that there are exactly $K$ intranets when the priorities are assigned uniformly at random among all $(M(M-1)/2)!$ ways of doing so.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case is described in a single line containing two integers $M$ and $K$: the number of machines and the target number of intranets, respectively.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the sought probability modulo the prime $10^9+7$ ($1000000007$). Represent the probability as an irreducible fraction $p/q$, where $p$ and $q$ are non-negative integers that minimize $p+q$. Then $y$ must equal $p \cdot q^{-1} \bmod (10^9+7)$, where $q^{-1}$ is the modular multiplicative inverse of $q$ with respect to the modulus $10^9+7$. It can be shown that under the constraints of this problem, such a number $y$ always exists and is unique.

• $1 \le T \le 50$.
• $1 \le K \le M/2$.

In Sample Case #1, consider the following situation. Let us call the $M=5$ machines $1, 2, 3, 4, 5$, and denote the link connecting machine $a$ and machine $b$ by $(a,b)$. Assume the priorities of links $(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)$ are $9, 8, 7, 6, 5, 4, 3, 2, 1, 10$, respectively. Then machines 1 and 2 use link $(1,2)$, machine 3 uses link $(1,3)$, and machines 4 and 5 use link $(4,5)$. Thus three links $(1,2), (1,3), (4,5)$ are active, and there are two intranets $\{1,2,3\}$ and $\{4,5\}$. Since $K=2$, this situation counts toward the answer.

There are $1555200$ ways to assign the priorities so that there are exactly $2$ intranets, out of $10!=3628800$ ways, so the probability is $3/7$. In Sample Case #2, the probability is $4/7$. In Sample Case #3, the probability is $1/21$.