```
#include <cmath>
class Solution {
public:
int findDerangement(int n) {
// recursion: !n = (n-1) * (!(n-1) + !(n-2))
// base case: n is 1 or 2
if (n == 1)
return 0;
if (n == 2)
return 1;
unsigned long long b = 1, a = 0, c = 0; // at least 64bits
int k = 3;
int m = (int)std::pow(10, 9) + 7;
while (k <= n){
c = ((k - 1) * (b + a)) % m;
a = b;
b = c;
k += 1;
}
return (int)c;
}
};
```