21053번 - Gig Combinatorics 다국어

문제

Your friend Tóti is an aspiring musician. He has written $n$ songs, each of which has a hype rating of either 1ドル,ドル 2ドル,ドル or 3ドル$. A higher hype rating means the song has more energy. Tóti is planning his first live performance and needs your help. He wants to know how many setlists he can make. A setlist consist of at least three songs, the first song must have hype rating 1ドル,ドル the last song must have hype rating 3ドル,ドル and all other songs must have hype rating 2ドル$. Tóti also wants to play the songs in the same order he wrote them.

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$.

제한

힌트