Solution Like Never Before
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    static final int MOD = 1_000_000_007;\n\n    public int countSubMultisets(List<Integer> nums, int l, int r) {\n        TreeMap<Integer, Integer> numsMap = new TreeMap<>();\n        for (int num : nums) {\n            numsMap.put(num, numsMap.getOrDefault(num, 0) + 1);\n        }\n\n        long[] cache = new long[r + 1];\n        cache[0] = 1;\n\n        for (Map.Entry<Integer, Integer> entry : numsMap.entrySet()) {\n            int num = entry.getKey();\n            int freq = entry.getValue();\n\n            // preprocessing\n            long[] pSum = Arrays.copyOf(cache, r + 1);\n            for (int i = 0; i <= r; ++i) {\n                if (i >= num) {\n                    pSum[i] += pSum[i - num];\n                    pSum[i] %= MOD;\n                }\n            }\n\n            // update dp cache\n            for (int i = r; i >= 0; --i) {\n                if (num > 0) {\n                    int j = i - (freq + 1) * num;\n                    cache[i] = pSum[i] - (j >= 0 ? pSum[j] : 0);\n                    cache[i] = Math.floorMod(cache[i], MOD);\n                } else {\n                    cache[i] *= freq + 1;\n                    cache[i] %= MOD;\n                }\n            }\n        }\n\n        long res = 0;\n        for (int i = l; i <= r; ++i) {\n            res += cache[i];\n            res %= MOD;\n        }\n        return (int) res;\n    }\n}\n```
['Java']