### Problem Statement

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}. Create a class Deranged with a function numDerangements that takes a int[] nums and return the number of derangements of nums.

### Definition

 Class: Deranged Method: numDerangements Parameters: int[] Returns: long Method signature: long numDerangements(int[] nums) (be sure your method is public)

### Notes

-The return value will fit in a 64-bit unsigned integer.

### Constraints

-nums will contain between 1 and 15 elements, inclusive.
-nums will only contain values between 0 and the number of elements in nums - 1, inclusive.

### Examples

0)

 `{1,1,2,2,3}`
`Returns: 4`
 The example from above.
1)

 `{0,0,0,1,1,1}`
`Returns: 1`
 The only derangement is {1,1,1,0,0,0}.
2)

 `{0,0,0,1,1,1,1}`
`Returns: 0`
 There is no way to arrange the numbers such that no 1 is where a 1 was originally.
3)

 `{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2}`
`Returns: 14`
4)

 ```{0,5,4,2,3,6,6} ```
`Returns: 640`
5)

 `{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}`
`Returns: 481066515734`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2013

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4685&pm=2013

Running Wild

#### Testers:

lbackstrom , brett1479