|
I |
The
Queue Input: Standard Input Output: Standard Output |
|
On some special
occasions Nadia’s company provide very special lunch for all employees of the
company. Before the food is served all of the employees must stand in a queue
in front of the food counter. The company applied a rule for standing in the
queue. The rule is nobody can stand anywhere in front of his supervisor in the
queue. For example if Abul is the supervisor of Babul and Abul stands in kth
position from the front of the queue, then Babul cannot stand at any position in
between 1 and k – 1 from front of the queue.
The
company has N employees and each of them has
exactly one supervisor except one who doesn’t have any supervisor.
You have
to calculate in how many ways the queue can be created. For this problem, you
can safely assume that in at least one way the queue can be created.
Input
Input
starts with an integer T (T is
around 700), the
number of test cases.
Each test case starts with a
line containing one integer N (1 ≤
N ≤ 1000). Each of the following N - 1 lines
will contain two integers a and b (1 ≤ a, b ≤ N and a ≠ b), which
denotes that a is the supervisor of b. For the sake of simplicity we are
representing each employee by an integer number.
Output
For each input case, output a
single line in the format “Case #: w”, here # is the
case number and w is the number of ways to create the queue. The number of ways
can be very large. You have to print the number modulo 1,000,000,007.
Sample
Input
Output for Sample Input
|
1 5 2 1 2 3 3 4 3 5 |
Case 1: 8 |
Problemsetter: Arifuzzaman Arif, Special Thanks: Jane Alam Jan, D. Kisman