22073번 - Конгресс юных любителей 다국어

37 фебратиста 3015 года конгресс юных любителей математики и философии был объявлен открытым. От каждой из n стран приехало по одному математику и одному философу. Через два часа состоится заседание, на котором будут присутствовать все участники, а организаторы еще не придумали как их рассадить.

В зале заседания стоит в ряд 2n стульев. Стулья бывают трех видов, причем на стуле первого типа может сидеть только математик, на стуле второго типа может сидеть только философ, а на стуле третьего типа может сидеть любой из участников конгресса.

К сожалению, это не единственная проблема, с которой столкнулись организаторы. Математики и философы — натуры чувствительные, поэтому математики и философы одной страны ненавидят друг друга, и следовательно они ни в коем случае не могут сидеть на соседних стульях. Также известно, что математики и философы не бросают своих в неловком положении, поэтому необходимо рассадить участников так, чтобы не было ни одного математика, с двух сторон от которого сидят философы, а также не должно быть ни одного философа, с двух сторон от которого сидят математики.

Организаторы поняли, что условия для принятия решения, кто будет сидеть на каком стуле, слишком сложные, а перебрать все способы слишком долго, так как их очень много. Помогите им для начала посчитать количество возможных способов рассадить участников конгресса. Выведите ответ по модулю 10⁹ + 7.

Первая строка содержит одно натуральное число t — количество тестов во входных данных. Далее следуют описания тестов.

Описание каждого теста содержит две строки. Первая строка описания содержит одно целое число n — количество стран. Вторая строка содержит 2n натуральных чисел от 1 до 3, где i-е число задает тип i-го стула. Число 1 означает, что на стуле может сидеть только математик, число 2 означает, что на стуле может сидеть только философ, а число 3 означает, что на стуле может сидеть любой участник конгресса.

Сумма n по всем тестам не превосходит 100.

Для каждого теста выведите число способов рассадить участников конгресса, взятое по модулю 10⁹ + 7.