Python numpy solution. Simple logic without tricks
Intuition\nIdea is knapsack using dynamic programming. In normal knapsack we need to iterate through each number and either add it to the set, or not. Here, mul
# Intuition\nIdea is knapsack using dynamic programming. In normal knapsack we need to iterate through each number and either add it to the set, or not. Here, multiset definition makes us to use Counter first, to compress numbers with their frequences.\n\n\n# Approach\n\n`DP[i, sm]` is a number of ways to get a sum `sm` using first `(i+1)` items from the counter.\n\nEach `DP[i, :]` depends only on `DP[i - 1, :]` - so we need to have only two of those at the same time in memory. I called them `DP` for the previous `i` and `NewDP` for the new `i`\n\n# Complexity\n- Time complexity: $$O(n*m)$$\n\n- Space complexity: $$O(n + m)$$\n\n# Code\n```\nfrom collections import Counter\nimport numpy as np\n\nMOD = int(1e9 + 7)\n\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n\n        # Replace nums to distinct values and their frequences\n        C = Counter(nums)\n\n        # DP[x] is a number of valid multisets to get sum of x\n        DP = np.zeros(r + 1, np.int64)\n        DP[0] = 1\n\n        for x, cnt in C.items():\n            if x == 0:\n                # Easy case, we can take any number of x from 0 to cnt, without changing the sum\n                DP = DP * (cnt + 1) % MOD\n\n            else:\n                # We could ignore x completely\n                NewDP = np.copy(DP)\n\n                # Or add x few times: from 1 to cnt\n                # Then new sum will be old sum + i*x\n                for shift in range(x, min(r, x * cnt) + 1, x):\n                    NewDP[shift:] += DP[:-shift]\n\n                # Replace old DP array with the new\n                DP = NewDP % MOD\n\n        # Need to return only for the l..r range sums\n        return DP[l:].sum() % MOD\n```
['Python3']