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

from functools import cache

MAX = 10 ** 9 + 7


class Solution:
    def numOfArrays(self, N: int, M: int, K: int) -> int:
        @cache
        def ways(n: int, m: int, k: int) -> int:
            """
            :param n:
            :param m:
            :param k:
            :return: number of ways an array (say A) can be constructed with constraints
                    1) len(A) == n
                    2) max(A) == m
                    3) search_cost(A) = k (definition of search_cost is in problem)
            """
            if n * m * k == 0:  # same as: (n == 0 or m == 0 or k == 0)
                return 0
            elif n == k == 1:
                # length is 1 and cost is 1 then m will be the only number in the
                # array. So total number of ways an array can be constructed is 1
                return 1
            else:
                return (
                    # let A be the one of the constructed arrays

                    # case-1: k-th search_cost is NOT incurred at (n - 1)th index. It 
                    #         means that m is already present in sub array A[:n - 1].
                    #         So last value in A could be any of [1, 2,..., m].
                    ways(n - 1, m, k) * m

                    +

                    # case-2: k-th search_cost is incurred at (n - 1)th index. If means 
                    #         that m is NOT in sub-array A[:n - 1]. So sub-array A[:n - 1] 
                    #         which is of length (n - 1) should consist of k - 1 search_costs 
                    #         and the largest value in A[:n - 1] could be any of [1, 2,..., m - 1]
                    sum(ways(n - 1, mx, k - 1) for mx in range(1, m))
                ) % MAX

        # As maximum of constructed array can be any of [1, 2,..., m] so summing all the ways
        return sum(ways(N, mx, K) for mx in range(1, M + 1)) % MAX
50100