long calc(int n, int k) {
        if (memo[n][k] != -1) {
            return memo[n][k];
        }
        if (k == 1) {
            return memo[n][k] = 1;
        }

        memo[n][k] = 0;
        for (int j = 1; j < k; j++) {
            if (n - k >= k - j) {
                memo[n][k] = (memo[n][k] + calc(k, j) * c[n - k - 1][k - j - 1]) % MOD;
            }
        }

        return memo[n][k];
    }