1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 2e5 + 1;
using ll = long long;
int N, M, K;
ll dp[1010][1010];
void Solution() {
    memset(dp, 0, sizeof dp);
    dp[1][0] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (j != 0) 
                dp[i][j] = dp[i-1][j-1] * (j + 1) % MOD;
            dp[i][j] = dp[i][j] + dp[i-1][j] * (j + 1) % MOD;
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        (ans += dp[N][i]) %= MOD;
    }
    cout << ans << '\n';
}
int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX