class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        # since 1 <= k <= 5 is constraint, we can declare the final ans list first
        ans = [0] * k
        prev_ans = [0] * k # record and update the ans
        for num in nums:
            # this round
            curr_counts = [0] * k
            # 1. only me
            remainder = num % k
            curr_counts[remainder] += 1

            # 2. me with prefix
            for r in range(k):
                if prev_ans[r] > 0:
                    new_remainder = (r * num) % k # (remain * num) % k = ((origin % k) * num) % k
                    curr_counts[new_remainder] += prev_ans[r] # all prev_ans with remainder r, add in to curr_counts

            # 3. dp update, summarize from nums[0] to current num
            # dp only need to remember previous ans (since prefix is consequent)
            prev_ans = curr_counts


            # summarize this round # from nums[0] to current num
            for r in range(k):
                ans[r] += curr_counts[r]

        return ans