<p>There are <code>n</code> uniquely-sized sticks whose lengths are integers from <code>1</code> to <code>n</code>. You want to arrange the sticks such that <strong>exactly</strong> <code>k</code>&nbsp;sticks are <strong>visible</strong> from the left. A stick&nbsp;is <strong>visible</strong> from the left if there are no <strong>longer</strong>&nbsp;sticks to the <strong>left</strong> of it.</p>

<ul>
	<li>For example, if the sticks are arranged <code>[<u>1</u>,<u>3</u>,2,<u>5</u>,4]</code>, then the sticks with lengths <code>1</code>, <code>3</code>, and <code>5</code> are visible from the left.</li>
</ul>

<p>Given <code>n</code> and <code>k</code>, return <em>the <strong>number</strong> of such arrangements</em>. Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3, k = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> [<u>1</u>,<u>3</u>,2], [<u>2</u>,<u>3</u>,1], and [<u>2</u>,1,<u>3</u>] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 5, k = 5
<strong>Output:</strong> 1
<strong>Explanation:</strong> [<u>1</u>,<u>2</u>,<u>3</u>,<u>4</u>,<u>5</u>] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 20, k = 11
<strong>Output:</strong> 647427950
<strong>Explanation:</strong> There are 647427950 (mod 10<sup>9 </sup>+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= n</code></li>
</ul>

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        # n = 5, k = 2
        # It is all about 5
        # . 5 . . . 
        # 4 . . . .
        #
        # n = 5, k = 3
        # 3 . . 4 5
        # . . 5 . .  -> 3
        # . 4 . . .  -> 3 (5 is already placed somewhere)
        # 3 . . . .  -> 3
        # 2 . . . .  -> 2
        # 1 . . . .  -> 1
        # BUT!! 2 1 5 4 3 is NOT good

        # dp[i][k] = SUM(dp[j-1][k-1])
        # WRONG, . . 1 2 3 is different from 1 2 3 . . 

        # @cache
        # def dp(i, K, free):
        #     # K = number of sticks you currently see
        #     # free = spots to the left of the smallest so far that are free

        #     if K == k and free > 0:
        #         # Already see k and you will eventually see more
        #         return 0
        #     if free == 0 and K != k:
        #         # Don't see k and can add more to be seen
        #         return 0
        #     if free + K < k:
        #         # Can never reach a valid arrangement anymore
        #         return 0

        #     if i == 0:
        #         return 1
        #     if free == 0:
        #         # You can place it on any of the open spots
        #         return math.factorial(i)

        #     # Place on one of the free spots
        #     ans = 0
        #     for j in range(1, free+1):
        #         ans += dp(i-1, K+1, free-j) 
        #     if i > free:
        #         # You can place it behind the largest so far
        #         ans += (i - free) * dp(i-1, K, free)

        #     return ans % 1_000_000_007

        # return dp(n, 0, n)

        @cache
        def dp(i, k):
            # dp[i][k] = after placing i sticks, see k
            # NOTE: stick i does not have size i in this solution
            if k == 0:
                return 0
            if i == k:
                # Only one way to place, which is:
                # placing them in increasing order
                return 1
            
            # Pick the largest stick as the right-most stick
            ans = dp(i-1, k-1) 
            # Pick any other of the (i-1) sticks to be the right-most
            # stick. Then this stick will never be seen from the left,
            # because the largest leftover stick will go on its left.
            ans += dp(i-1, k) * (i-1)
            return ans % 1_000_000_007

        return dp(n, k)
313668