If you couldn't remember the formula, I find these two videos really helpful.

https://www.youtube.com/watch?v=51-b2mgZVNY

https://www.youtube.com/watch?v=nwpzBE9IwJQ

With this formula, we can define P0 = #permutations that no number is in its original position.

P(one number) = #permutations one number is in its original position. C(n, 1) * (n-1)! = n!/1!

P(two number) = two are in their position. C(n, 2) * (n-2) ! = n!/2!

P(n numbers) = C(n, n) * (n-n)! = 1

It's also easy to see that:

P(m number) = n!/m! = (m+1)*P(m+1 number)

So based on the formula the number of cases when some number is in its own position is:

P(one number) - P(two number) + .... + (-1) ^(n+1) P(n number)

And all permutation of n numbers are n!

so P0 = n! - P(one number) + P(two numbers) + ..(-1)^n P(n numbers)

```
class Solution {
public:
const int M = 1e9 + 7;
int findDerangement(int n) {
long long res = 0;
long long pn = 1;
for(int i=n; i>=1; --i) {
res = ( res + (i % 2 == 0 ? 1 : -1) * pn + M)%M;
pn = pn * i % M;
}
return (pn + M + res)%M;
}
};
```