<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:
        md = 10 ** 9 + 7
        dp = [0] * (r + 1)
        dp[0] = 1
        mx_nonzero = 0
        f_dict = Counter(nums)
        nums2 = sorted(f_dict.keys(), reverse=True)
        if not nums2[-1]: nums2.pop()
        n = len(nums2)
        cumu_rev = sum(x * f_dict[x] for x in nums2)
        for idx in reversed(range(n)):
            num = nums2[idx]
            # The largest possible collective contribution from the
            # iterations after this one to any multiset sum
            cumu_rev -= num * f_dict[num]
            # The smallest index in the DP array that can influence
            # the final result (and so the smallest index that needs
            # to be updated)
            mn = max(0, l - cumu_rev)
            # The largest index in the DP that can be non-zero after
            # the current iteration
            mx_nonzero = min(r, mx_nonzero + num * f_dict[num])
            # Iterating over different congruences modulo num of the
            # endpoints of the sliding windows (which themselves slide
            # by increments of num to the left, thus requiring up to
            # num sliding windows for complete coverage)
            for i1 in reversed(range(max(mx_nonzero - num + 1, mn), mx_nonzero + 1)):
                # The largest frequency of num that can appear in a
                # multiset with sum i1
                f0 = min(f_dict[num], i1 // num)
                # The initial sum over the sliding window
                curr = sum(dp[i1 - num * j] for j in range(1, f0 + 1)) % md
                # The (possibly empty) range of indices (in increments of num)
                # for which the left end of the sliding window is no less than
                # num, and so when shifting the sliding window to the left by a
                # displacement of num, updating the sliding window value requires
                # adding a new value on the left end
                i_rng1 = (i1, min(i1, max((i1 % num) + (f0 * num), max(mn, num) - 1)))
                # The (possibly empty) range of indices (in increments of num)
                # for which the left end of the sliding window is strictly less than
                # num, and so when shifting the sliding window to the left by a
                # displacement of num, updating the sliding window value does not
                # require adding a new value on the left end
                i_rng2 = (i_rng1[1], min(i_rng1[1], max(mn, num) - 1))
                for i in range(*i_rng1, -num):
                    dp[i] = (dp[i] + curr) % md
                    curr = (curr - dp[i - num] + dp[i - (f0 + 1) * num]) % md
                for i in range(*i_rng2, -num):
                    dp[i] = (dp[i] + curr) % md
                    curr = (curr - dp[i - num]) % md
        # As adding any number of 0s to a multiset does not affect
        # its sum, the zero count's net effect is to multiply the
        # result when ignoring the zeros by the zero count plus 1
        return ((sum(dp[l:]) % md) * (f_dict.get(0, 0) + 1)) % md
828