<p>A sequence is <strong>special</strong> if it consists of a <strong>positive</strong> number of <code>0</code>s, followed by a <strong>positive</strong> number of <code>1</code>s, then a <strong>positive</strong> number of <code>2</code>s.</p>

<ul>
	<li>For example, <code>[0,1,2]</code> and <code>[0,0,1,1,1,2]</code> are special.</li>
	<li>In contrast, <code>[2,1,0]</code>, <code>[1]</code>, and <code>[0,1,2,0]</code> are not special.</li>
</ul>

<p>Given an array <code>nums</code> (consisting of <strong>only</strong> integers <code>0</code>, <code>1</code>, and <code>2</code>), return<em> the <strong>number of different subsequences</strong> that are special</em>. Since the answer may be very large, <strong>return it modulo </strong><code>10<sup>9</sup> + 7</code>.</p>

<p>A <strong>subsequence</strong> of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are <strong>different</strong> if the <strong>set of indices</strong> chosen are different.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,2,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The special subsequences are bolded [<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>,2], [<strong><u>0</u></strong>,<strong><u>1</u></strong>,2,<strong><u>2</u></strong>], and [<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>,<strong><u>2</u></strong>].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,0,0]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no special subsequences in [2,2,0,0].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,1,2,0,1,2]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The special subsequences are bolded:
- [<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>,0,1,2]
- [<strong><u>0</u></strong>,<strong><u>1</u></strong>,2,0,1,<strong><u>2</u></strong>]
- [<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>,0,1,<strong><u>2</u></strong>]
- [<strong><u>0</u></strong>,<strong><u>1</u></strong>,2,0,<strong><u>1</u></strong>,<strong><u>2</u></strong>]
- [<strong><u>0</u></strong>,1,2,<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>]
- [<strong><u>0</u></strong>,1,2,0,<strong><u>1</u></strong>,<strong><u>2</u></strong>]
- [0,1,2,<strong><u>0</u></strong>,<strong><u>1</u></strong>,<strong><u>2</u></strong>]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 2</code></li>
</ul>

class Solution:
    # [0 1 2 0 1 2]
    # at index 5, we see that we have 1s at indeces 4 and 1
    # before index 4, there are 2 0s => res += 3 (0 4 5), (3 4 5), (0 3 4 5)
    # before index 1, there is 1 0 => res += 2 (0 1 5), (0 1 4 5)
    # so we need to keep track of how many 0s are before each index
    # and how many ones are at and after each index
    # prefix0 = [0 1 1 1 2 2]
    # prefix1 = [2 2 1 1 1 0]
    # res += res
    # prefix0[1] = 1 => res += 1 * (1 + 1)//2 * prefix1[1]
    # prefix0[4] = 2 => res += 2 * (2 + 1)/2 * prefix1[4] = 3
    # prefix0[1] = 1 => res += 1 * (1 + 1)/2 * prefix1[1] = 2
    # 0 0 0 1 2
    # 0 1 2 => res = 3
    # 0 0 1 2 => res = 6
    # 0 0 0 1 2 => res = 7
    # so it's prefix[0]
    # it goes:
    # how many ways can we choose a 1?
    # for each way we can choose a 1, how many way can we choose 0s?
    # [0 1 2 0 1 2]
    # i = 2. we can choose a 1 1 way, and from there ,we can choose a 0 1 way => res = 1
    # i = 5. we can choose a 1 2 ways, and from there, we can choose a 0 3 ways and 1 way => res = 5
    # we can also choose both 1s, and from there, we can choose a 0 1 more way => res = 6
    # finally, we previously had 1 special subseqeucne, so we can add a 2 to that one => res = 7
    # for each way we can choose a 1, how many ways can we choose 0s?
    # easy: 2^numZeros - 1
    # i = 5, indeces = [1, 4]
    # prefix0[4] = 2 => res += 3 * 1
    # prefix0[1] = 1 => res += 1 * 2
    # 1 * 4
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10 ** 9 + 7
        length = len(nums)
        prefix0 = 0
        dp = 0
        res = 0
        for i in range(length):
            if nums[i] == 0:
                prefix0 += 1
            elif nums[i] == 1:
                dp = (pow(2, prefix0, mod) - 1 + 2 * dp) % mod
            else:
                res = (2 * res + dp) % mod
        return res % mod
        
1629