At last, Mr. X has managed to return to the school at which he formerly
taught, with the intention of confronting his suspicious successor, Mr. Y.
However, it appears that Mr. Y has fortified his position — he has brainwashed
all of his students into believing that he's the world's best teacher through
the timeless ploy of replacing classes with extra recesses. There's no way
that Mr. Y can be thrown out of the school without first compromising his
students' support!

There are **N** students in Mr. Y's class, with IDs from 1 to **N**. In an
attempt to maximize security, Mr. Y has arranged them into a hierarchical
structure, with each student _i_ either reporting to a commanding student
**Ci**, or not reporting to any other student (indicated by **Ci** = 0).
There's exactly one student _i_ for whom **Ci** = 0, who is the class leader.

A _chain of command_ is a sequence of one or more students going up the
hierarchical structure starting from some student _i_ and ending somewhere
between _i_ and the class leader (inclusive): _i_ → **Ci** → **CCi** → etc.
It's guaranteed that, for each student _i_, there exists a _chain of command_
beginning at them and ending at the class leader.

Initially, all **N** students are under Mr. Y's control. However, Mr. X is
about to perform some bribery of his own. One by one, in order from 1 to
**N**, Mr. X will bribe each student with healthy snacks. After the first _b_
bribes, students 1.._b_ will be under Mr. X's control instead of Mr. Y's.

After each of the **N** bribes, Mr. X would like to evaluate the vulnerability
of Mr. Y's class to a potential takeover. To do so, he'll determine **N**
hypothetical values: for each student _i_, he'll compute the maximum length
that a _controlled chain_ beginning with student _i_ could possibly have if 0
or more _promotions_ were to first take place (or 0 if no such chain could
exist).

A _controlled chain_ is a _chain of command_ consisting exclusively of
students under Mr. X's control. A _promotion_ is a modification to the class
structure in which Mr. X selects a certain student _j_ with a commanding
student _c_ = **Cj** (such that _c_ ≠ 0 and _c_ ≠ _i_), expels student _c_
(removing them from the class entirely), and brings _j_ up to occupy _c_'s
former place (setting **Cj** to **Cc**, and for each other student _k_ such
that **Ck** = _c_, now setting **Ck** to j). Note that each of these
hypothetical values should be considered independently of the others; Mr. X
will never actually perform any _promotions_ and permanently alter the class
structure.

In order to reduce the size of the output, these **N2** values should be
aggregated into a single integer as follows: Letting **Sb** be the sum of the
**N** students' maximum _controlled chain_ lengths after the first _b_
students have been bribed, output (**S1** * **S2** * ... * **SN**) modulo
1,000,000,007.

### Input

Input begins with an integer **T**, the number of times Mr. X needs to wrest
control from Mr. Y. For each time, there is first a line containing the
integer **N**. Then, **N** lines follow, the _i_th of which contains the
integer **Ci**.

### Output

For the _i_th time, print a line containing "Case #_i_: " followed by a single
integer, the product of all **N** sums of maximum _controlled chain_ lengths,
modulo 1,000,000,007.

### Constraints

1 ≤ **T** ≤ 80
1 ≤ **N** ≤ 800,000
0 ≤ **Ci** ≤ **N**

### Explanation of Sample

In the first case, after the first student has been bribed, a length-1
_controlled chain_ can begin at student 1, while no _controlled chain_ can
begin at student 2. Once the second student has also been bribed, a length-1
_controlled chain_ can still begin at student 1, while a length-2 _controlled
chain_ may now begin at student 2 (2 → 1). This results in a total answer of
(1 + 0) * (1 + 2) = 3 (modulo 1,000,000,007).

In the second case, after the first two students have been bribed, a length-2
_controlled chain_ can begin at student 1 (1 → 2) if student 1 gets promoted
(replacing student 3). The total answer comes out to (1 + 0 + 0) * (2 + 1 + 0)
* (3 + 1 + 2) = 18 (modulo 1,000,000,007).

In the third case, after the first two students have been bribed, a length-2
_controlled chain_ may begin at student 1 (1 → 2) if student 2 gets promoted
(replacing student 3), and a length-1 _controlled chain_ can similarly begin
at student 2 (2 → 1) if student 1 gets promoted (replacing student 3). The
total answer comes out to (1 + 0 + 0) * (2 + 2 + 0) * (2 + 2 + 1) = 20 (modulo
1,000,000,007). _

In the fourth case, the total answer is (1 + 0 + 0 + 0 + 0) * (2 + 2 + 0 + 0 +
0) * (2 + 3 + 2 + 0 + 0) * (2 + 3 + 2 + 1 + 0) * (2 + 3 + 2 + 1 + 3) = 2464
(modulo 1,000,000,007).

In the fifth case, the total answer is 1 * 3 * 7 * 11 * 14 * 16 * 20 * 28 * 33
* 39 * 44 * 47 = 790446393 (modulo 1,000,000,007).