공연 셋리스트 조합

친구 Tóti는 음악가를 꿈꾼다. 그는 곡을 $n$개 썼고, 각 곡에는 $1$, $2$, $3$ 중 하나의 흥분도가 매겨져 있다. 흥분도가 높을수록 곡의 에너지가 크다. Tóti는 첫 라이브 공연을 준비 중인데, 당신의 도움이 필요하다. 그는 몇 개의 셋리스트를 만들 수 있는지 알고 싶어 한다. 셋리스트는 곡을 세 곡 이상 포함하고, 첫 곡의 흥분도는 $1$, 마지막 곡의 흥분도는 $3$, 나머지 곡의 흥분도는 모두 $2$여야 한다. Tóti는 또한 곡을 자신이 쓴 순서대로 연주하려고 한다.

Tóti가 쓴 순서대로 각 곡의 흥분도가 주어질 때, 그가 만들 수 있는 셋리스트의 수를 구하시오.

첫째 줄에 Tóti가 쓴 곡의 수 $n$이 주어진다. ($1 \leq n \leq 10^6$)

둘째 줄에 $n$개의 정수가 주어지며, 각 정수는 $\{1, 2, 3\}$에 속하고, Tóti가 쓴 순서대로 각 곡의 흥분도를 나타낸다.

Tóti가 만들 수 있는 셋리스트의 수를 출력한다. 이 수는 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.