1866. Number of Ways to Rearrange Sticks With K Sticks Visible

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

• For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

class Solution {
    int dp[1001][1001];
    int mod = 1e9 + 7;
public:
    long rearrangeSticks(int n, int k) {
        if(n == k) return 1;
        if(!k) return 0;
        if(!dp[n][k]) {
            return dp[n][k] = (rearrangeSticks(n - 1, k - 1) + rearrangeSticks(n - 1, k) * (n - 1))%mod; 
        }
        return dp[n][k];
    }
};