[c++] 100% [100ms]
\ntypedef long long ll;\nclass Solution {\npublic:\n    const static int mod = (int)(1e9 +7);\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n   
```\ntypedef long long ll;\nclass Solution {\npublic:\n    const static int mod = (int)(1e9 +7);\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());        \n        int m = nums.back();\n        \n        vector<int> cnt(m + 1, 0);\n        int sum = 0;\n        for (auto v : nums) { \n            cnt[v]++;\n            sum += v;\n        }\n        if (l > sum) return 0;\n        \n        vector<pair<int, int>> vp;\n        for (int i = 1; i <= m; i++) {\n            if (cnt[i] == 0) continue;\n            vp.push_back({i, cnt[i]});\n        }\n        \n        vector<ll> dp(sum + 1, 0);\n        dp[0] =1 + cnt[0];\n        int cur = 0;\n        for (auto[x, y] : vp) {\n            cur = cur + x * y;          \n            for (int i = cur; i > cur - x; i--) {\n                int cs = 0;\n                int a = i - x;\n                for (int b = a; b >= max(0,i - x * y); b -= x) cs = (cs + dp[b]) % mod;\n                dp[i] = (cs + dp[i]) % mod;\n                for (int j = i - x; j > 0; j -= x) {\n                    int b = j - x * y;\n                    if (a >= 0) cs = (cs + mod - dp[a]) % mod;\n                    if (b >= 0) cs = (cs + dp[b]) % mod;\n                    dp[j] = (cs + dp[j]) % mod;\n                    a = j - x;\n                }\n            }\n        }\n        \n        long long ans = 0;\n        for (int i = l;  i <= min(sum, r); i++) {\n            ans = (ans + dp[i]) % mod;\n        }\n        return ans;\n    }\n};\n```
[]