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


# https://www.youtube.com/watch?v=y4Pn4jxCw7E

# 此題思路是從circular permutations發想，然後以DP來實作。
# 此題本質上是Sterling numbers的求解。
# S[n][k] = S[i-1][j-1] + S[i-1][j] * (i-1)

# # Choosing m from n numbers to construct a permutation.
# A(n, m) = n! / (n-m)!
# # Choosing m from n numbers to construct a circular permutation.
# H(n, m) = n!/ (n-m)! / m

# # e.g. H(n, n) = n!/n, Why (n!/n)? 
# # This formula arises because, in a circle, 
# # any item can serve as the starting point. So, for n items, 
# #there are n possible starting points. However, 
# #all these starting points lead to the same circular arrangement, 
# #so we divide the total permutations by n.

# # intuition: considered as, fixing the head, running permutation for the rest.


# # Using n numbers to construct m circular permutations.
# dp[i][j]: the numer of ways that we can use first i numbers to construct 
# j circular permutations.
# 1. if i-th element is a new circular permutation:
#     dp[i][j] = dp[i-1][j-1]
# 2. insert the i-th element to the previous j circular permutation:
#     dp[i][j] = dp[i-1][j] * (j-1)

# # https://leetcode.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/solutions/1211070/c-detailed-explanation-with-thought-process-dp/
# another thinking way:
# We select the tallest of the n sticks. There's only one such 
# stick and this stick will finally be visible from the left. 
# And so we are left with the sub-problem (n - 1, k - 1).
# We select a stick that's not the tallest one. We can do this by 
# selecting any of the n - 1 sticks that are not the tallest one. 
# So there are n - 1 sub-problems and each of them is (n - 1, k). 
# This stick we selected will not be visible from the left, so we still 
# gotta select k sticks from the remaining pile that will be visible, 
# that's why the sub-problem has k, and not k - 1.

# s.t.
# [ a1 x ... x] [a2 y ... y] [a3 z ... z] ...

# 也就是dp[i][j]的組合式共有兩種情況，當i是目前加入後最右邊的位置：
# 1. 該i是目前最大值，比前面任何i-1值都大，代表新的j的值是前面i-1數值裡的visible+1，也就是j+1:
#     dp[i][j] = dp[i-1][j-1]
# 2. 該i不是最大值，因此i-1數值裡的visible數量跟新加入i一樣，而總共有n-1個i值要加入：
#     dp[i][j] = dp[i-1][j] * (n-1)
# 可以看作是circular permutation，因此如果把i插入到i-1裡面


class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        if n == k:
            return 1
        if k == 0:
            return 0
        
        dp = [[0] * (k+1) for _ in range(n+1)]
        M = 1e9+7
        dp[0][0] = 1
        for i in range(1, n+1):
            for j in range(1, min(k+1, n+1)):
                dp[i][j] += (dp[i-1][j-1] + (dp[i-1][j] * (i-1))%M ) % M
        return int(dp[n][k])
        pass
1840