The Staggered formula is D(n) = (n1) [D(n2) + D(n1)]：
For the k th element, it has k1 positions and there are two possibilities for its position

1.It's not in the first element, so it's going to be the same thing as D(n  1)

2.It's in the position of the first element,so there are two elements in the deranged position.
So it's going to be the same thing as D(n  2)
so res = ((i1)(dn1+dn2))%1000000007;*
why we use long not int:
a(11) = 14684570
a(12) = 176214841
a(13) = 12 * (a(12) + a(11)) = 2290792932 > Integer.MAX_VALUE
public int findDerangement(int n) {
long dn2 = 0, dn1 = 1;
long res = n==1 ? 0 : 1;
for (int i = 3; i <= n; i++){
res = ((i1) * (dn1+dn2))%1000000007;
dn2 = dn1;
dn1 = res;
}
return (int) res;
}