题目描述

Your friend Tóti is an aspiring musician. He has written nn 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?

输入格式

输出格式

样例

9 
1 1 1 2 2 2 3 3 3

63

8 
1 2 1 2 3 1 2 3

15

提示

by jifengzhiyin