C++ || DP || Similar to Distinct Subsequences II
\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        vector<long long int> dp(binary.size(), 0);\n        unordered_map
```\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string binary) {\n        vector<long long int> dp(binary.size(), 0);\n        unordered_map<char, int>last;\n        last[\'0\'] = -1;\n        last[\'1\'] = -1;\n        int index = 0;\n        int n = binary.size();\n        int found = 0;\n        int mod = 1e9 + 7;\n        while(index < n && binary[index] == \'0\'){\n            index++;\n            found = 1;\n        }\n        if(index == n)\n            return 1;\n        dp[index] = 1;\n        last[1] = index;\n        for(int i = index+ 1; i <n ; i++){\n            found = binary[i] == \'0\' ? 1 : found;\n            dp[i] = (dp[i-1]*2) % mod;\n            if(last[binary[i]] - 1 >= 0)\n                dp[i] -= dp[last[binary[i]] - 1];\n            dp[i] %= mod;\n            last[binary[i]] = i;\n        }\n       // cout<<dp[n-1]<<endl;\n        return (dp[n-1] < 0 ? dp[n-1] + mod : dp[n-1]) + (found == 1 ? 1 : 0);\n    }\n};\n```
['Dynamic Programming', 'C']