## 1221 - Derangement

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 3

Solved: 2

Description
A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}.
Now give you n nums, can you find the number of derangements of nums.
Input
The first line is a number T which refers to the test cases.
For each case,The first number represent n descripted above. Then follow n nums. nums will contain between 1 and 15 elements, inclusive.And nums will only contain values between 0 and the number of elements in nums - 1, inclusive.Each number separated by a space.
Output
The only line represents the result.if the result is no less than 40003, output it, or divide it by 40003 and output the remainder.
sample input
```2
5 1 1 2 2 3
6 0 0 0 1 1 1
```
sample output
```4
1
```
hint
source
Xiangsanzi, HUST Programming Contest 2007
© 2015 HUST ACMICPC TEAM. All Right Reserved.