| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 5 | 2 | 100.000% |
Чтобы избежать многочисленных войн, в средние века любили проводить большие собрания, где все могли мирно обсудить интересующие вопросы. Во время такого собрания всех присутствующих рассаживали за большой круглый стол. Скоро пройдет очередное собрание, куда прибудут представители $n$ стран. Каждая страна отправила на это собрание ровно двух человек --- экономиста и политика. Каждый из делегатов хорошо разбирается только в своей сфере, поэтому обсуждать он будет только ее.
Перед организаторами этого собрания возникла проблема рассадить представителей всех стран. Понятно, что нельзя допустить ситуации, чтобы на трех подряд местах сидели люди, которые обсуждают одно и то же (экономику или политику). В этом случае люди начнут формировать коалиции по три человека, и цель собрания не будет достигнута.
Также известно, что экономистам нравится сидеть на красных креслах, политикам --- на синих, а на фиолетовых --- и те, и другие. Про каждое из кресел, которые стоят вокруг стола, известен его цвет. Главному мудрецу организующей страны было поручено посчитать количество возможных способов рассадки гостей.
Пронумеруем все места вокруг стола числами от одного до 2ドル\times{n}$. Два способа считаются различными, если существует такое место $i,ドル что в этих способах на нем сидят люди из различных стран или люди, обсуждающие разные стороны политики.
Первая строка входного файла содержит одно целое число $n$ (2ドル \le n \le 150$) --- количество стран-участниц собрания. Во второй строке содержится 2ドル\times{n}$ чисел. $i$-ое число равно 0, 1 или 2, если $i$-ое кресло фиолетовое, красное или синее соответственно.
В единственной строке выведите количество возможных вариантов размещения представителей стран по модулю 10ドル^9 + 7$.
2 1 2 1 2
4
3 1 2 0 0 0 2
108