1535. Build Array Where You Can Find The Maximum Exactly K Comparisons

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        MOD = 10**9 + 7
        
        # dp[i][max_so_far][search_cost] = number of ways
        # to build array of length i with max value max_so_far and search_cost
        # Since we only need previous row, we can optimize space
        
        # dp[max_val][cost] = ways to build current position with max=max_val and cost=cost
        dp = [[0] * (k + 1) for _ in range(m + 1)]
        
        # Initialize: for position 1, if we place value j, cost=1 and max=j
        for j in range(1, m + 1):
            dp[j][1] = 1
        
        # Fill for positions 2 to n
        for i in range(2, n + 1):
            new_dp = [[0] * (k + 1) for _ in range(m + 1)]
            
            # Precompute prefix sums for optimization
            # prefix[c] = sum of dp[j][c] for j from 1 to max_val-1
            
            for max_val in range(1, m + 1):
                for cost in range(1, k + 1):
                    # Case 1: Place a value <= current max (max_val)
                    # This doesn't increase cost, we can place any of 1..max_val
                    new_dp[max_val][cost] = (dp[max_val][cost] * max_val) % MOD
                    
                    # Case 2: The new element becomes the new maximum
                    # Previous max was < max_val, cost was cost-1
                    for prev_max in range(1, max_val):
                        new_dp[max_val][cost] = (new_dp[max_val][cost] + dp[prev_max][cost - 1]) % MOD
            
            dp = new_dp
        
        # Sum all ways with any max value and exactly k cost
        result = 0
        for max_val in range(1, m + 1):
            result = (result + dp[max_val][k]) % MOD
        
        return result