830. Count Special Subsequences (Mod 10^9+7)

Count subsequences of form [0..0,1..1,2..2] in array of 0/1/2, mod p.

Input: Integer array of 0/1/2.

Output: Integer.

Examples

Example 1

Input: [0,1,2]
Output: 1
Explanation: Only [0,1,2].

Example 2

Input: [0,1,2,0,1,2]
Output: 7
Explanation: 7 ways.

Example 3

Input: [2,2,2]
Output: 0
Explanation: No 0s.