<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:

        BIG = 10**9+7

        facts = [1]

        def factmod(n: int) -> int:
            """n! mod BIG"""
            while len(facts) <= n:
                facts.append((facts[-1]*len(facts)) % BIG)

            return facts[n]

        @cache
        def mminv(n: int) -> int:
            """Returns modular multiplicative inverse of n mod BIG"""
            return pow(n % BIG, BIG-2, BIG) # long story, see Euler's Theorem, BIG is prime

        # start with n sticks that would be visible if placed, and 0 that would be invisible
        # suppose we have
        #   > s shorter sticks than placed thus far
        #   > l longer sticks than placed thus far
        #   > and we need to place k more

        # then our options are
        #   > place a shorter stick: s-=1, l unchanged, k unchanged
        #   > place a longer stick:
        #       > place longer stick i=1..l: s += i-1, l -= i, k -= 1

        # @cache
        # def ways(s: int, l: int, k: int) -> int:
        #     if l < k: return 0 # not enough possibly visible sticks left
        #     if l and not k: return 0 # 1+ stick means at least one will be visible from here, but k is zero
        #     if l == k:
        #         # (s+l) choose s positions will have short numbers in any order: (s+l) choose s * s!
        #         # the rest have the long sticks ascending
        #         # (s+l) choose s * s! = (s+l)! / s! / (s+l-s)! * s! == (s+l)! / l!
        #         return factmod(s+l)*mminv(factmod(l)) % BIG

        #     ans = 0

        #     if s:
        #         # can place any of the shorter sticks
        #         ans += s*ways(s-1, l, k)
            
        #     # for each longer stick i=1..l and we rebalance shorter vs longer sticks
        #     ans += sum(ways(s+i-1, l-i, k-1) for i in range(1, l+1))

        #     return ans % BIG

        # return ways(0, n, k)

        ###### the above works, but it's too slow. O(N**2 K) DP is too expensive

        # so we need something faster: fewer variables probably

        # for any arrangement the first stick is visible
        #    > suppose that stick has height h
        #       > that means we have h-1 shorter sticks we can freely permute
        #       > and we have n-h higher sticks in the remaining positions: looks like n-h, k!!
        #         > we know that n-h >= k is required so we can limit our range of iteration

        # @cache
        # def ways(n: int, k: int) -> int:
        #     if k == 1:
        #         # place largest stick first, permute n-1 remaining ones
        #         return factmod(n-1)

        #     if k == n:
        #         return 1 # all must be visible: no flexibility here

        #     else:
        #         # any stick we choose here is visible
        #         # suppose we put stick h first
        #         #    > the h-1 shorter sticks can appear in any of the n-1 remaining positions in any permutation
        #         #        > that's (n-1 choose h-1) locations * (h-1)! == (n-1)! / (n-1-h+1)! == (n-1)! / (n-h)!
        #         #    > of the remaining n-h sticks, there are ways(n-h, k-1) of arranging those
        #         #        > we know that we need n-h >= k-1 so we'll limit the h iteration range to n-(k-1) >= h
        #         # the common (n-1)! term can be deferred on until the end
        #         ans = 0
        #         for h in range(1, n-(k-1)+1):
        #             ans += ways(n-h, k-1) * mminv(factmod(n-h)) # 1/(n-h)! * ways(n-h, k-1) parts
        #             ans %= BIG

        #         ans %= BIG
        #         return (ans * factmod(n-1)) % BIG # include the common (n-1)! part

        # return ways(n, k)

        ##### (n,k) calls (n-1,k-1), (n-2, k) ..., (k, k)
        #  so we have O((n-k)*k) states
        # and each does O(n-k) work, ouch
        
        # we can place any stick of height h at the current position
        #   > the h-1 shorter can be in any permutation at later n-1 choose h-1 positions
        #   > can defer to ways(n-h, k-1) for later sticks
        #
        # can we fast-forward through part of the ways(n-1, k-1)?
        #
        # we have to choose k visible sticks: n choose k
        #   those k have to appear in order
        #   shorter sticks in any order: but shorter depends on the permutation of heights, ouch
        #
        #   h
        #   h
        #   h
        #   h  {shorter: any location and permutation works} {taller: n-h taller sticks of which k-1 must be visible}

        # I think I need a different angle on this entirely
        #
        # Suppose we have n sticks left of which k must be visible, we'll account for shorter sticks as before
        # so each subproblem can start with n,k
        #
        # the tallest must be visible of course, anything after is invisible
        #    if n==k there's one way: ordered
        #    if n > k then we can
        #      > tallest at position k: (n-1) choose (k-1) to order up front, last one behind
        #      > tallest at position k+1: choose k to be up front, in order, then swap any pair so one is invisible, rest permuted behind
        #      > tallest at position k+2: choose k+1 up front in order, then swap 2
        #      > tallest and position m: 
        #           > (n-1) choose (m-1) * ways(m-1, k-1)   # pick m-1 of the values less than tallest, put them in first m
        #           > (n-m)!                                # we placed m-1 before and tallest at m: permute the remaining n-m after
        #
        #     total is (n-1)! / (m-1)! / (n-m)! * ways(m-1, k-1) * (n-m)!
        #              (n-1)! / (m-1)! * ways(m-1, k-1)
        #
        #    sum this over m:  (n-1)! [1/1! ways(1, k-1) + 1/2! ways(2, k-1) + 1/3! ways(3, k-1)]
        


        # Can we reduce to a single variable, n-k?
        # Or build in O(1) on a smaller subproblem?

        # for 1 stick, 1 visible: 1 way
        # for n sticks, 1 visible: (n-1)!

        # for 2 sticks, 2 visible: 1
        # 3 sticks, 2 visible:
        #     h=1 first: 2 sticks, 1 visible
        #     h=2 first: 1 stick, 1 visible + perms of h=1



        #### Let's try something totally different: what if we insert visible sticks???
        ##
        # start with highest stick: n-1, k-1 to go
        # next stick: insert to right: n-2, k-1 to go
        #                    to left: n-2, k-2 to go
        #
        # as we go in reverse order, highest to shortest, there's only one insert position to make it visible: prepend
        #     all other positions give the same number of 

        # so for n=5, k=3:
        #      place 5: n=4, k=2
        #      /                 \
        #    prepend 4: n=3, k=1   append 4: n=3, k=2

        @cache
        def ways(h, k):
            if h == k: return 1 # prepend n times
            if k == 0:
                # insert rest so they're not visible
                #   > since we're placing h, we placed (n-h) already
                #   > so we can place h after any of the (n-h)
                #     and h-1 after any of the (n-h+1)
                #     ...
                #     1 after any of the (n-1)
                #   > for a total of (n-1)! / (n-h-1)!
                return factmod(n-1)*mminv(factmod(n-h-1)) % BIG

            # else we have two ways to go:
            #    prepend: need k-1 more visible and continue with h-1
            #    else: already placed (n-h) so we can insert after any of these: (n-h) places
            #      for each we do something new with h-1, so product of configurations
            return (ways(h-1, k-1) + (n-h)*ways(h-1, k)) % BIG

        return ways(n, k)
343018