Problem Description

Frog loves symmetry. When he sees an array of numbers, the first thing he'll do, is to count the number of sub-arrays which is symmetric (when read from left to right, or in the reverse direction, it will be the same). The more sub-arrays frog finds, the happier he will be.

We human beings are frog's best friends. For each array, we will shuffle the array, changing some numbers' positions if possible, to mostly satisfy the frog.

Now we wonder the maximum number of symmetric sub-arrays frog will find. And the number of different arrays to reach this maximum result. Two arrays $a$ and $b$ are considered different, if at least for one position $i$, there are $a_i \neq b_i$.

Input

First line contains an integer $T$, which indicates the number of test cases.

Every test case begins with an integers $N$, which is the length of the array.

The second line contains $N$ numbers $a_1$, $a_2$, $\cdots$, $a_N$, indicating the elements in the array.

$1 \leq T \leq 100$.

for 60% data, $1 \leq N \leq 10$ and $1 \leq a_i \leq 5$.

for 80% data, $1 \leq N \leq 100$ and $1 \leq a_i \leq 20$.

for 100% data, $1 \leq N \leq 3000$ and $1 \leq a_i \leq 70$.

Output

For every test case, you should output "Case #x: y z", where $x$ indicates the case number and counts from $1$, $y$ is the maximum number of symmetric sub-arrays frog will find, and $z$ is the number of different arrays to reach this maximum result.

Because $z$ could be very large, just mod it with $10^9 + 7$.

2
3
1 2 3
4
1 3 2 3

Case #1: 3 6
Case #2: 5 10

Hint

In the second sample, {1,3,2,3} itself is one of the solutions, there are 5 sub-arrays which is symmetric, {1}, {3}, {2}, {3}(for a second time), and {3,2,3}. But {3,1,2,3} is not, which only contains 4 symmetric sub-arrays.