<p>You are given a <strong>0-indexed</strong> array <code>nums</code> of non-negative integers, and two integers <code>l</code> and <code>r</code>.</p>

<p>Return <em>the <strong>count of sub-multisets</strong> within</em> <code>nums</code> <em>where the sum of elements in each subset falls within the inclusive range of</em> <code>[l, r]</code>.</p>

<p>Since the answer may be large, return it modulo <code>10<sup>9 </sup>+ 7</code>.</p>

<p>A <strong>sub-multiset</strong> is an <strong>unordered</strong> collection of elements of the array in which a given value <code>x</code> can occur <code>0, 1, ..., occ[x]</code> times, where <code>occ[x]</code> is the number of occurrences of <code>x</code> in the array.</p>

<p><strong>Note</strong> that:</p>

<ul>
	<li>Two <strong>sub-multisets</strong> are the same if sorting both sub-multisets results in identical multisets.</li>
	<li>The sum of an <strong>empty</strong> multiset is <code>0</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,2,3], l = 6, r = 6
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only subset of nums that has a sum of 6 is {1, 2, 3}.
</pre>

<p><strong>Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,4,2,7], l = 1, r = 5
<strong>Output:</strong> 7
<strong>Explanation:</strong> The subsets of nums that have a sum within the range [1, 5] are {1}, {2}, {4}, {2, 2}, {1, 2}, {1, 4}, and {1, 2, 2}.
</pre>

<p><strong>Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,3,5,2], l = 3, r = 5
<strong>Output:</strong> 9
<strong>Explanation:</strong> The subsets of nums that have a sum within the range [3, 5] are {3}, {5}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {1, 1, 2}, {1, 1, 3}, and {1, 2, 2}.</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2 * 10<sup>4</sup></code></li>
	<li>Sum of <code>nums</code> does not exceed <code>2 * 10<sup>4</sup></code>.</li>
	<li><code>0 &lt;= l &lt;= r &lt;= 2 * 10<sup>4</sup></code></li>
</ul>

class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        '''
        dp[i][j] to record the count of submultisets
            i: use the first i num in nums
            j: sum up to j
        freqs = {num:freq}
        for k in range(1, freq+1):
            dp[i+1][j] = dp[i][j] + dp[i][j-k*num] if j-k*num>0
        add up all the nums from l to r
        limited choices: loop from right to left
        optimization: space
        '''
        MOD = 10**9 + 7
        total = sum(nums)
        if l > total:
            return 0
        
        r = min(r, total)
        freqs = Counter(nums)
        dp = [freqs[0] + 1] + [0] * r
        del freqs[0]  # Remove frequency of 0 since it does not contribute to positive sums
        
        s = 0
        for x, c in freqs.items():
            new_dp = dp.copy()
            s = min(s + x * c, r)  # The maximum sum achievable so far
            for j in range(x, s + 1):  # Limit the range to s
                new_dp[j] += new_dp[j - x]
                if j >= (c + 1) * x:
                    new_dp[j] -= dp[j - (c + 1) * x]
                new_dp[j] %= MOD
            dp = new_dp
        
        return sum(dp[l:]) % MOD
        # MOD = 10**9+7
        # total = sum(nums)
        # if l > total:
        #     return 0
        # r = min(r, total)
        # freqs = Counter(nums)
        # nums = list(set(nums))  # 确保 nums 是唯一的
        # dp = [0] * (r + 1)
        # dp[0] = 1
        
        # upper_bound = 0
        # for num in nums:
        #     freq = freqs[num]
        #     upper_bound = min(r, upper_bound + freq * num)
        #     new_dp = dp[:] 
        #     if num == 0:
        #         bound = freq
        #     else:
        #         bound = min(freq, r // num)
        #     for j in range(r + 1):
        #         if dp[j] > 0:
        #             for k in range(1, bound + 1):
        #                 if j + k * num <= r:
        #                     new_dp[j + k * num] = (new_dp[j + k * num] + dp[j]) % MOD
        #     dp = new_dp
        
        # res = sum(dp[l:r + 1]) % MOD
        # return res

        

        # total = sum(nums)
        # if l > total:
        #     return 0
        # r = min(r, total)
        # freqs = Counter(nums)
        # nums = set(nums)
        # dp = [[0]*(r+1) for _ in range(len(nums)+1)]
        # dp[0][0] = 1
        # upper_bound = 0
        # for i,num in enumerate(nums):
        #     freq = freqs[num]
        #     upper_bound = min(r, upper_bound+freq*num)
        #     for j in range(upper_bound+1):
        #         dp[i+1][j] = dp[i][j]
        #         if num == 0:
        #             bound = freq
        #         else:
        #             bound = min(freq,j//num)
        #         for k in range(1, bound+1):
        #             dp[i+1][j] += dp[i][j-k*num]
        #         dp[i+1][j] %= MOD
        # res = sum(dp[-1][l:r+1]) % MOD
        # return res
1020