Arrange n sticks of distinct lengths 1 through n in a row. Looking from the left, a stick is visible exactly when it is taller than every stick before it. Count the arrangements with exactly k visible sticks, and return the count modulo 1000000007. Each length must appear exactly once.
Example 1:
Input: n = 3
k = 1
Output: 2Explanation: The tallest stick must come first. The arrangements [3,1,2] and [3,2,1] show only that first stick, giving 2 arrangements.
Example 2:
Input: n = 4
k = 4
Output: 1Explanation: All four sticks are visible only when every stick is taller than its predecessor: [1,2,3,4].
Example 3:
Input: n = 4
k = 3
Output: 6Explanation: The six arrangements are [1,2,4,3], [1,3,2,4], [1,3,4,2], [2,1,3,4], [2,3,1,4], and [2,3,4,1]. Each has exactly three new tallest sticks when scanned from left to right.
Constraints:
1 <= k <= n <= 1000