Given the hype rating of each of Tóti’s songs in the order he wrote them, how many setlists can he make?
The first line of input consists of an integer $n$ ($1 \leq n \leq 10^6$), the number of songs Tóti has written. The second line consists of $n$ integers, each in $\{ 1, 2, 3\} $, giving the hype ratings of the $n$ songs in the order they were written.
Output the number of setlists Tóti can make. Since this number can be large, print it modulo $10^9 + 7$.
Sample Input 1 | Sample Output 1 |
---|---|
9 1 1 1 2 2 2 3 3 3 |
63 |
Sample Input 2 | Sample Output 2 |
---|---|
8 1 2 1 2 3 1 2 3 |
15 |