You are given a binary string binary. A subsequence of binary is considered good if it is not empty and has no leading zeros (with the exception of "0").

Find the number of unique good subsequences of binary.


	For example, if binary = "001", then all the good subsequences are ["0", "0", "1"], so the unique good subsequences are "0" and "1". Note that subsequences "00", "01", and "001" are not good because they have leading zeros.


Return the number of unique good subsequences of binary. Since the answer may be very large, return it modulo 109 + 7.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

&nbsp;
Example 1:

Input: binary = "001"
Output: 2
Explanation: The good subsequences of binary are ["0", "0", "1"].
The unique good subsequences are "0" and "1".


Example 2:

Input: binary = "11"
Output: 2
Explanation: The good subsequences of binary are ["1", "1", "11"].
The unique good subsequences are "1" and "11".

Example 3:

Input: binary = "101"
Output: 5
Explanation: The good subsequences of binary are ["1", "0", "1", "10", "11", "101"]. 
The unique good subsequences are "0", "1", "10", "11", and "101".


&nbsp;
Constraints:


	1 &lt;= binary.length &lt;= 105
	binary consists of only '0's and '1's.


class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        
        
        # zero_as_last: the count of S0, good sequence ending in 0
        # one_as_last : the count of S1: good sequence ending in 1
        # zero_exist:   existence flag of 0 in given binary
        
        dp = {"zero_as_last": 0, "one_as_last": 0, "zero_exist": 0}
        
        for bit in map(int, binary):
            
            if bit:
                # current good = ( S0 concate with 1 ) + ( S1 concate with 1 ) + 1 alone
                # + "1" is allowed because leading 1 is valid by description
                dp["one_as_last"] = dp["zero_as_last"] + dp["one_as_last"] + 1
            
            else:
                # current good = ( S0 concate with 0 ) + ( S1 concate with 0 ) 
                # + "0" is NOT allowed because leading 0 is invalid by description
                dp["zero_as_last"] = dp["zero_as_last"] + dp["one_as_last"]
            
            # check the existence of 0
            dp["zero_exist"] |= (1-bit)
        
        
        return sum( dp.values() ) % ( 10**9 + 7 )
class Solution {
    public int numberOfUniqueGoodSubsequences(String binary) {
        int initialZeroCount= 0;
        while(initialZeroCount < binary.length() && binary.charAt(initialZeroCount) == '0') initialZeroCount++;
        if(initialZeroCount == binary.length()) return 1;
        long[] dp = new long[binary.length()];
        dp[initialZeroCount] = 1;
        int lastOne = 0, lastZero = 0;
        long mod = (long) Math.pow(10, 9)+7;
        for(int i=initialZeroCount+1;i<binary.length();i++){
            int j = binary.charAt(i) == '1' ? lastOne : lastZero;
            long dup = j > 0 ? dp[j-1] : 0;
            dp[i] = 2 * dp[i-1] - dup;
            if(dp[i] < 0) dp[i] += mod;
            dp[i] %= mod;
            if(binary.charAt(i) == '0') lastZero = i;
            else lastOne = i;
        }
        
        int hasZero = 0;
        if(binary.contains("0")) hasZero = 1;
        
        
        return (int) (dp[binary.length()-1] + hasZero);
    }
}
class Solution {
    int MOD = 1000000007;
public:
    int numberOfUniqueGoodSubsequences(string binary) {
        int zero = 0;
        long long ones = 0;
        long long zeros = 0;
        
        for (int i = binary.size() - 1; i >= 0; --i) {
            if (binary[i] == '1') {
                ones = (ones + zeros + 1) % MOD;
            } else {
                zero = 1;
                zeros = (ones + zeros + 1) % MOD;
            }
        }
        return (ones + zero) % MOD;
    }
};
const MOD = 1000000007;

var numberOfUniqueGoodSubsequences = function(binary) {
    let endsZero = 0;
    let endsOne = 0;
    let hasZero = 0;
    for (let i = 0; i < binary.length; i++) {
        if (binary[i] === '1') {
            endsOne = (endsZero + endsOne + 1) % MOD;
        } else {
            endsZero = (endsZero + endsOne) % MOD;
            hasZero = 1;
        }
    }
    return (endsZero + endsOne + hasZero) % MOD;
};
Number of Unique Good Subsequences