0(n) Dynamic Programming solution
\n\n# Complexity\n- Time complexity:\n0(n)\n- Space complexity:\n0(n)\n# Code\n\nconst int mod = 1e9 + 7;\nint norm(int x) {\n    if (x < 0) {\n        x += mod
\n\n# Complexity\n- Time complexity:\n0(n)\n- Space complexity:\n0(n)\n# Code\n```\nconst int mod = 1e9 + 7;\nint norm(int x) {\n    if (x < 0) {\n        x += mod;\n    }\n    if (x >= mod) {\n        x -= mod;\n    }\n    return x;\n}\ntemplate<class T>\nT power(T a, int b) {\n    T res = 1;\n    for (; b; b /= 2, a *= a) {\n        if (b % 2) {\n            res *= a;\n        }\n    }\n    return res;\n}\n\n\nstruct Mint {\n    int x;\n    Mint(int val = 0) {\n      this->x = norm(val);\n    }\n    int val() const {\n        return x;\n    }\n   // operator overloading \n    Mint operator-() const {\n        return Mint(norm(mod - x));\n    }\n  \n    Mint &operator*=(const Mint &rhs) {\n        x = (x * 1LL * rhs.x) % mod;\n        return *this;\n    }\n    Mint &operator+=(const Mint &rhs) {\n        x = norm(x + rhs.x);\n        return *this;\n    }\n    Mint &operator-=(const Mint &rhs) {\n        x = norm(x - rhs.x);\n        return *this;\n    }\n    Mint &operator/=(const Mint &rhs) {\n        return *this *= rhs.inv();\n    }\n    friend Mint operator*(const Mint &lhs, const Mint &rhs) {\n        Mint res = lhs;\n        res *= rhs;\n        return res;\n    }\n    friend Mint operator+(const Mint &lhs, const Mint &rhs) {\n        Mint res = lhs;\n        res += rhs;\n        return res;\n    }\n    friend Mint operator-(const Mint &lhs, const Mint &rhs) {\n        Mint res = lhs;\n        res -= rhs;\n        return res;\n    }\n    friend Mint operator/(const Mint &lhs, const Mint &rhs) {\n        Mint res = lhs;\n        res /= rhs;\n        return res;\n    }\n    \n    friend ostream & operator<<(ostream &out, const Mint &c){\n      out<<c.x;\n      return out;\n    }\n\n   // important functions\n        Mint inv() const {\n        assert(x != 0);\n        return power(*this, mod - 2);\n    }\n   \n\n    \n\n};\n\nvector<Mint> fact;\nvector<Mint> inv_fact;\n \nvoid gen_fact(int n){\n   assert(n >= 1);\n      \n   fact.resize(n + 1);\n   inv_fact.resize(n + 1);\n   fact[0] = 1;\n   fact[1] = 1;\n\n   for(int i = 2;i<=n;i++){\n      fact[i] = fact[i - 1] * i;\n      inv_fact[i] = fact[i].inv();\n   }\n\n}\n\nMint C(int n,int r){\n      if(r > n) return 0;\n      assert((int) fact.size() > n);\n      return fact[n] * Mint(fact[r] * fact[n - r]).inv();\n}\n\nMint P(int n,int r){\n   return C(n,r) * fact[r];\n}  \n\nclass Solution {\npublic:\n    int numberOfUniqueGoodSubsequences(string s) {\n int n = (int) s.size();\n   \n\n  vector<int> pos(2,-1);\n  vector<Mint> dp(n + 2);\n  for(int i = n - 1;i>=0;i--){\n   dp[i] = dp[i + 1] * 2;\n   if(pos[s[i] - \'0\'] == -1){\n      dp[i] += 1;\n   }else{\n      dp[i] -= dp[pos[s[i]-\'0\']];\n   }\n   pos[s[i] - \'0\'] = i + 1;\n }\n\n for(int i = 0;i<n;i++){\n   if(s[i] == \'0\'){\n      dp[0] -= dp[i + 1];\n      break;\n   }\n }  \n  return dp[0].x;\n      }\n};\n```
['Dynamic Programming', 'C++']