Apricot Rules LLC is developing a new simplified networking protocol and wants to show off their routing algorithm. In their design, a network consists of machines numbered from
to
, and each pair of machines is connected by a direct link. Each of the links is given a unique integer priority value between
and
and each machine routes traffic according to those priorities.
Unfortunately, the routing algorithm is too aggressive and will route all traffic from a machine through the highest priority link connected to it. This may make some groups of machines isolated from others.
Formally, we say that a machine uses a link
if (and only if)
is the highest priority link connected to
. We also say that a link is active if it is used by at least one of the two machines it connects. Given the link priorities, the original network becomes partitioned into disjoint intranets. Two machines belong to the same intranet if and only if there is some path between them using only active links.


For example, as seen in the left image above, only the links with priorities and
are active. This creates two disjoint intranets. However, in the example on the right, three links are active, which results in one intranet consisting of all
machines.
As part of the quality assurance team at Apricot Rules LLC, you are investigating the extent of the problem. You are interested in knowing the probability of there being exactly intranets if the priorities are assigned uniformly at random from among the
ways of doing so.
Input Specification
The first line of the input gives the number of test cases, .
test cases follow. Each test case is described in a single line containing two integers
and
: the number of machines and the target number of intranets, respectively.
Output Specification
For each test case, output one line containing Case #x: y
, where is the test case number (starting from
) and
is the sought probability computed modulo the prime
, which is defined precisely as follows. Represent the probability as as an irreducible fraction
(with
and
being non-negative integers that minimize
). Then,
must equal
, where
is the modular multiplicative inverse of
with respect to the modulus
. It can be shown that under the constraints of this problem, such a number
always exists and is unique.
Limits
.
.
Test Set 1
Time limit: 20 seconds.
.
Test Set 2
Time limit: 60 seconds.
.
Sample Input
3
5 2
5 1
6 3
Sample Output
Case #1: 428571432
Case #2: 571428576
Case #3: 47619048
Explanation for Sample
In Sample Case #1, consider the following situation. Let's call machines
and denote the link connecting machine
and machine
by
. Assume that the priorities of links
are
, respectively. Then machines
and
use link
, machine
uses link
, and machines
and
use link
. Thus three links
are active, and there are two intranets
and
. Since
, this situation counts the answer.

We can find that there are ways to assign the priorities to have exactly
intranets among
ways, so the probability is
.
In Sample Case #2, the probability is .
In Sample Case #3, the probability is .
Note
This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >60.000s
regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.
Comments