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