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$.
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$.
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$.