```
def findDerangement(self, N):
MOD = 10**9 + 7
X, Y = 1, 0
for n in xrange(2, N+1):
X, Y = Y, (n - 1) * (X + Y) % MOD
return Y
```

Let `D(N)`

be the required answer. The recursion for the number of derangements of N is: `D(N) = (N-1) * (D(N-1) + D(N-2))`

. With this recursion in hand, the problem becomes similar to finding the N-th fibonacci number.

To prove it, suppose there are people and hats labelled `1...N`

. We want the number of ways to put a hat on each person such that no person is wearing their hat. The first person has N-1 choices to put on a hat, say he wears hat X. Now consider what hat person X is wearing. Either he takes hat 1, and we have `D(N-2)`

ways to arrange the remaining hats among people; or he doesn't take hat 1, which if we relabelled it as hat X, would have `D(N-1)`

ways to arrange the remaining hats.