<p>You are given three integers <code>n</code>, <code>m</code> and <code>k</code>. Consider the following algorithm to find the maximum element of an array of positive integers:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/02/e.png" style="width: 424px; height: 372px;" />
<p>You should build the array arr which has the following properties:</p>

<ul>
	<li><code>arr</code> has exactly <code>n</code> integers.</li>
	<li><code>1 &lt;= arr[i] &lt;= m</code> where <code>(0 &lt;= i &lt; n)</code>.</li>
	<li>After applying the mentioned algorithm to <code>arr</code>, the value <code>search_cost</code> is equal to <code>k</code>.</li>
</ul>

<p>Return <em>the number of ways</em> to build the array <code>arr</code> under the mentioned conditions. As the answer may grow large, the answer <strong>must be</strong> computed modulo <code>10<sup>9</sup> + 7</code>.</p>

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

<pre>
<strong>Input:</strong> n = 2, m = 3, k = 1
<strong>Output:</strong> 6
<strong>Explanation:</strong> The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
</pre>

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

<pre>
<strong>Input:</strong> n = 5, m = 2, k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no possible arrays that satisfy the mentioned conditions.
</pre>

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

<pre>
<strong>Input:</strong> n = 9, m = 1, k = 1
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
</pre>

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

<ul>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>1 &lt;= m &lt;= 100</code></li>
	<li><code>0 &lt;= k &lt;= n</code></li>
</ul>

"""
Given n, m and k
1 <= arr[i] <= m where (0 <= i < n).

if k > m or k > n
    return 0
example: k = 2, m = 1
[1,2] has a 2 that is greater than 1.


Suppose k = 3
|
|               * xxxxxx   
|       * xxxxxx  xxxxxx
|         xxxxxx  xxxxxx
|* xxxxx  xxxxxx  xxxxxx
|  xxxxx  xxxxxx  xxxxxx
|  xxxxx  xxxxxx  xxxxxx
|________________________

*  
    - the * is free moving horizontally, as long as monotonicity is held.
    Equation to calculated the num of permutations = 
        n! / (k! * (n-k)!)

    - the * is also free moving vertically, as long as monotonicity is held.
    Equation:
        m! / (m - k)! <-- a for loop could also simulate this as m * (m-1) * (m-2) ..

    - the number of combinations of values between the asterisks:
    Equestion:


|
|               *   
| *
|        
| 
|  
|*  
|________________________


m == the max allowed value in the array
n == len(arr)
k == the kth time max < arr[i] is entered into


m   n   k       result
1   1   1       1
2   1   1       2
3   1   1       3

3   2   1       

33
32
22
31
21
11



if k = 1,
    then the solution is 1 ** (n-1) + 2 ** (n-1) .. m ** n - 1



Is the answer n * k / 2 ?

This involves combinatorics.



n! / (k! * (n-k)!)

Example 2:
Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisfy the mentioned conditions.
Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]
 

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n


'''
Words to call each section:
    - interval
    - segment
    - group
    - partition
    - block
    - slice
    - batch
    - chunk
    - bin
    https://chatgpt.com/c/84e20e60-6e94-4e97-a713-41120409b7b2


What are simpler related problems?
- Find the number of ways to partition an array of stars into N partitions.
- Find the number of ways to partition an array of numbers such that the first number in each partition is the largest number in the partition

"""


# What happens when the # of bars and len(arr) are equal?
class Solution:
    def numOfArrays_(self, n: int, m: int, k: int) -> int:

        if m < k:
            return 0
        dp = [[1] * m] + [[0] * m for _ in range(k - 1)]
        mod = 10**9 + 7
        for _ in range(n - 1):
            for i in range(k - 1, -1, -1):
                cur = 0
                for j in range(m):
                    dp[i][j] = (dp[i][j] * (j + 1) + cur) % mod
                    if i > 0:
                        cur = (cur + dp[i - 1][j]) % mod
        return sum(dp[-1]) % mod

    # m = the maximum value allowed in the array
    # n = len(arr)
    # k = the kth time max < arr[i] is entered into

    
    def numOfArrays_(self, n: int, m: int, k: int) -> int:
        @lru_cache(None)
        def dp(i, h, k):
            # Base Cases
            if i == n and k == 0:
                return 1
            if i == n or k < 0:
                return 0

            # Recursive Call and Summation
            total_ways = 0
            for j in range(1, m + 1):                
                total_ways += dp(i + 1, max(h, j), k - (h < j))
            return total_ways % 1000000007

        # Final Return Statement
        return dp(0, -1, k)
        '''
        In this line:
        total_ways += dp(i + 1, max(h, j), k - (j > h))
        What is:
            i + 1?
                i is the number of columns we're created so far. It is the number of columns across all sections. So cc | ccc | c would represent 6 columns across 3 sections.
            max(h, j)
                h is the maximum height of all column heights so far.
                j is the height of the current column
                When the height of the current column exceeds the recorded maximum height so far, then the maximum height we're recording must be updated. It's not literally in the code, but in a sense it is, because the updated max height is passed to subsequent column generation recursively.
            k - (j > h)
                Think of k as a countdown counter that decrements the number of new max height columns needed. `k - (j > h)` decrements `k` when the current column is the tallest so far, when its height is a new max height. We want the maximum height to change only k times throughout the process of generating columns. When the current column is the tallest, then we have k - 1 more new max heights to go. So `k - (j > h)` decrements k from k down to 0. Think of k as a countdown counter.
        '''

    def numOfArrays(self, n: int, m: int, k: int) -> int:
        max_bars_left = k
        p_slots_count = n
        p_max_height = m

        """
        height = 3, width 1
        combinations = 0**0 + 1**0 + 2**0
        """
        from functools import cache

        @cache
        def get_combs_of_rect(rect_height, rect_width):
            return (rect_height ** (rect_width - 1)) % 1000000007
        @cache
        def fn(start_idx, max_bars_left, start_height):
            if max_bars_left == 1:
                rect_width = p_slots_count - start_idx
                # print("base case")
                temp = 0
                for height in range(start_height, p_max_height + 1):
                    temp = (temp + get_combs_of_rect(height, rect_width)) % 1000000007
                return temp
            combinations = 0
            for next_idx in range(start_idx + 1, p_slots_count - max_bars_left + 2):
                for height in range(
                    start_height, p_max_height - max_bars_left + 2
                ):
                    # print("intermediate case")
                    cur_combinations = get_combs_of_rect(
                        height, next_idx - start_idx
                    )
                    next_combinations = fn(next_idx, max_bars_left - 1, height + 1)
                    combinations += (
                        cur_combinations * next_combinations
                    )  # ) % 1000000007
            return combinations % 1000000007

        return fn(0, max_bars_left, 1)
    """
    Why the + 2 in:
        p_slots_count - max_bars_left + 2):
    It's because it's equivalent to:
        p_slots_count - (max_bars_left - 1) + 1):
    The current call is consuming a max bar. So we have max_bars_left - 1 max-bar instances left for subproblems to use. Regarding the rightmost `+ 1`, it's added to match the fact that we're starting at 1 and not 0, shown by: `start_idx + 1`

    So suppose we had 2 slots, and we call fn with max_bars_left = 2.
    That would mean
        for next_idx in range(start_idx + 1, p_slots_count - max_bars_left + 2):
    translates to
        for next_idx in range(0 + 1, 2 - 2 + 2):
    which simplifies to
        for next_idx in range(1, 2)


    Why is start_height = 0 for the initial call:
        return fn(0, max_bars_left, 1) 
    It's because it's the lowerbound height of the rectangle.
    """



    # Note: See my note "test-june-2024.py"
    def numOfArrays_(self, n: int, m: int, k: int) -> int:
        max_bars_left = k
        p_slots_count = n
        p_max_height = m

        """
        height = 3, width 1
        combinations = 0**0 + 1**0 + 2**0
        """
        from functools import cache

        @cache
        def get_combs_of_rect(rect_height, rect_width):
            return (rect_height ** (rect_width - 1)) % 1000000007        
        def get_combs_of_rect_(start_height_idx, rect_width):
            combinations = 0
            for cur_height in range(start_height_idx + 1, p_max_height + 1):
                combinations += cur_height ** (rect_width - 1)
            return combinations % 1000000007

        @cache
        def fn(width, max_bars_left, start_height_idx):
            if max_bars_left == 0:
                rect_width = width
                # print("base case")
                temp = 0
                for height in range(start_height_idx, p_max_height):
                    temp = (temp + get_combs_of_rect(height, rect_width)) % 1000000007
                return temp            
            combinations = 0
            for end in range(1, width - max_bars_left + 1):
                for next_height_idx in range(
                    start_height_idx + 1, p_max_height - max_bars_left + 1
                ):
                    # print("intermediate case")

                    rect_width = end - 1
                    rect_height = next_height_idx - 1
                    cur_combinations = (rect_height**rect_width) % 1000000007

                    next_combinations = (
                        fn(width - end, max_bars_left - 1, next_height_idx) % 1000000007
                    )
                    combinations += (cur_combinations * next_combinations) % 1000000007
            return combinations % 1000000007

        return fn(p_slots_count, max_bars_left - 1, 0)

26300