Build Array Where You Can Find The Maximum Exactly K Comparisons LeetCode solution in Python

1
class Solution:
2
    def numOfArrays(self, n: int, m: int, k: int) -> int:
3
        @cache
4
        def dp(a, b, c):
5
            if a == n:
6
                return c == k
7
            return (b * dp(a + 1, b, c) if b >= 1 else 0) + sum(
8
                dp(a + 1, i, c + 1) for i in range(b + 1, m + 1)
9
            )
10

11
        return dp(0, 0, 0) % (10**9 + 7)