## Saturday, December 3, 2016

### Tara's Beautiful Permutations

Tara has an array, , consisting of  integers where each integer occurs at most  times in the array.
Let's define  to be a permutation of  where  is the  element of permutation . Tara thinks a permutation is beautiful if there is no index  such that  where .
You are given  queries where each query consists of some array . For each , help Tara count the number of possible beautiful permutations of the  integers in  and print the count, modulo , on a new line.
Note: Two permutations,  and , are considered to be different if and only if there exists an index  such that  and .
Input Format
The first line contains a single integer, , denoting the number of queries. The  subsequent lines describe each query in the following form:
1. The first line contains an integer, , denoting the number of elements in array .
2. The second line contains  space-separated integers describing the respective values of  in array .
Constraints
• Each integer in  can occur at most  times.
For  of the maximum score:
• The sum of  over all queries does not exceed .
For  of the maximum score:
Output Format
For each query, print the the number of possible beautiful permutations, modulo , on a new line.
Sample Input 0
3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0
1
2
2

Explanation 0
We perform the following  queries:
1. Array  and there is only one good permutation:

Thus, we print the result of  on a new line.
2. Array  and there are two good permutations:

Thus, we print the result of  on a new line.
3. Array  and there are two good permutations:

For demonstration purposes, the following two permutations are invalid (i.e., not good):

Because we only want the number of good permutations, we print the result of  on a new line.