# LeetCode - 1955. Count Number of Special Subsequences
### 題目網址：https://leetcode.com/problems/count-number-of-special-subsequences/
###### tags: `LeetCode` `Hard` `字串` `動態規劃（Dynamic Programming）`

/*
    -LeetCode format-
    Problem: 1955. Count Number of Special Subsequences
    Difficulty: Hard
    
    by Inversionpeter
*/



#define MOD 1000000007u

static const auto Initialize = []{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        unsigned endWith0 = 0, endWith1 = 0, endWith2 = 0;
        for (int &i : nums)
            switch (i) {
                case 0:
                    endWith0 = (endWith0 << 1) + 1;
                    if (endWith0 >= MOD)
                        endWith0 -= MOD;
                    break;
                case 1:
                    endWith1 = (endWith1 << 1) + endWith0;
                    while (endWith1 >= MOD)
                        endWith1 -= MOD;
                    break;
                default:
                    endWith2 = (endWith2 << 1) + endWith1;
                    while (endWith2 >= MOD)
                        endWith2 -= MOD;
                    break;
            }
        return endWith2;
    }
};