1866

class Solution {
public:
    #define ll long long
    ll mod = int(1e9)+7LL;
    int rearrangeSticks(int n, int k) {
        if(k > n) return 0;
        if(n == k) return 1;

        // Create DP table.
        ll dp[n+1][k+1];
        memset(dp, 0, sizeof dp);

        // Initialize table.
        for(int i=0; i<=k; i++)
            dp[i][i] = 1;

        // Fill the table in bottom up fashion.
        // 1. Place tallest stick at end and add dp(n-1, k-1) ways.
        // 2. Place one of the smallest sticks at end and add (n-1)*dp(n-1,k) ways.
        for(int i=1; i<=n; i++)
            for(int j=1; j<=min(i,k); j++)
                dp[i][j] = (dp[i-1][j-1] + (dp[i-1][j]*(i-1))%mod)%mod;

        return dp[n][k];
    }
};