Problem C
Gig Combinatorics
Given the hype rating of each of Tóti’s songs in the order he wrote them, how many setlists can he make?
Input
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
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 |