DP (Knapsack)
\n\n# Code\n\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        int n = nums.size()
\n\n# Code\n```\nclass Solution {\npublic:\n    const int mod = 1e9 + 7;\n    int countSubMultisets(vector<int>& nums, int l, int r) {\n        int n = nums.size();\n        int sum = 0, mx = 0;\n        vector<int> freq(2e4 + 1);\n        set<int> s;\n        for(int i=0;i<n;i++){\n            freq[nums[i]] ++;\n            mx = max(mx, nums[i]);\n            sum += nums[i];\n            s.insert(nums[i]);\n        }\n        vector<int> v;\n        for(auto j : s){\n            v.push_back(j);\n        }\n        sort(v.begin(), v.end());\n        n = v.size();\n        vector<vector<int>> dp(n, vector<int>(sum + 1));\n        for(int i=0;i<=freq[v[0]];i++){\n            dp[0][i * v[0]] += 1;\n        }\n        vector<int> ndp(sum + 1);\n        if(n > 1){\n            for(int i=0;i<=sum;i++){\n                if(i - v[1] >= 0){\n                    ndp[i] = (ndp[i - v[1]] + dp[0][i])%mod;\n                    if(i - ((freq[v[1]] + 1) * v[1]) >= 0){\n                        ndp[i] = (ndp[i] - dp[0][i - ((freq[v[1]] + 1) * v[1])] + mod)%mod;\n                    }\n                }\n                else{\n                    ndp[i] = dp[0][i];\n                }\n            }\n        }\n        for(int i=1;i<n;i++){\n            for(int j=0;j<=sum;j++){\n                dp[i][j] = (dp[i][j] + ndp[j])%mod;\n            }\n            if(i + 1 < n){\n                ndp = vector<int> (sum + 1);\n                for(int j=0;j<=sum;j++){\n                    if(j - v[i+1] >= 0){\n                        ndp[j] = (ndp[j - v[i+1]] + dp[i][j])%mod;\n                        if(j - ((freq[v[i+1]] + 1) * v[i+1]) >= 0){\n                            ndp[j] = (ndp[j] - dp[i][j - ((freq[v[i+1]] + 1) * v[i+1])] + mod)%mod;\n                        }\n                    }\n                    else{\n                        ndp[j] = dp[i][j];\n                    }\n                }\n            }\n        }\n        int ans = 0;\n        if(l > sum){\n            return 0;\n        }\n        for(int i=l;i<=min(sum, r);i++){\n            ans = (ans + dp[n-1][i])%mod;\n        }\n        return ans;\n    }\n};\n```
['C++']