Number of Ways to Rearrange Sticks With K Sticks Visible - Problem

#include <stdio.h>
#include <stdlib.h>

const int MOD = 1000000007;

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int n, int k) {
    // dp[i][j] = ways to arrange i sticks with j visible
    long long** dp = (long long**)malloc((n + 1) * sizeof(long long*));
    for (int i = 0; i <= n; i++) {
        dp[i] = (long long*)calloc(k + 1, sizeof(long long));
    }
    
    dp[0][0] = 1;  // Base case
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(i, k); j++) {
            // Case 1: stick i is visible (placed at front)
            if (j >= 1) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
            }
            
            // Case 2: stick i is hidden (placed among first i-1 positions)
            dp[i][j] = (dp[i][j] + (dp[i-1][j] * (i-1)) % MOD) % MOD;
        }
    }
    
    int result = dp[n][k];
    
    // Free memory
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    int result = solution(n, k);
    printf("%d\n", result);
    
    return 0;
}