• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int findDerangement(int n) {
dp.resize(n + 1);
return find(n);
}

private:
constexpr static int kMod = 1e9 + 7;
vector<int> dp;

int find(int i) {
if (i == 0)
return 1;
if (i == 1)
return 0;
if (dp[i])
return dp[i];
return dp[i] = (i - 1L) * (find(i - 1) + find(i - 2)) % kMod;
}
};
``````

## JAVA

``````class Solution {
public int findDerangement(int n) {
dp = new Long[n + 1];
return (int) find(n);
}

private static final int kMod = (int) 1e9 + 7;
private Long[] dp;

private long find(int i) {
if (i == 0)
return 1;
if (i == 1)
return 0;
if (dp[i] != null)
return dp[i];
return dp[i] = (i - 1) * (find(i - 1) + find(i - 2)) % kMod;
}
}
``````

## Python

``````class Solution:
def findDerangement(self, n: int) -> int:
kMod = int(1e9) + 7

@lru_cache(None)
def dp(i: int) -> int:
if i == 0:
return 1
if i == 1:
return 0
return (i - 1) * (dp(i - 1) + dp(i - 2)) % kMod

return dp(n)
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int findDerangement(int n) {
constexpr int kMod = 1e9 + 7;
vector<int> dp(n + 1);

dp[0] = 1;

for (int i = 2; i <= n; ++i)
dp[i] = (i - 1L) * (dp[i - 1] + dp[i - 2]) % kMod;

return dp[n];
}
};
``````

## JAVA

``````class Solution {
public int findDerangement(int n) {
final int kMod = (int) 1e9 + 7;
int[] dp = new int[n + 1];

dp[0] = 1;

for (int i = 2; i <= n; ++i)
dp[i] = (int) ((i - 1L) * (dp[i - 1] + dp[i - 2]) % kMod);

return dp[n];
}
}
``````

## Python

``````class Solution:
def findDerangement(self, n: int) -> int:
kMod = int(1e9) + 7
dp = [1] + [0] * n

for i in range(2, n + 1):
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % kMod

return dp[n]
``````