Мажоритарным элементом последовательности целых положительных чисел называется число, которое встречается не менее чем в половине её элементов.

Последовательность называется хорошей, если все её непустые непрерывные подпоследовательности имеют хотя бы один мажоритарный элемент. Например, $[1, 2, 1, 1, 3]$ является хорошей, так как подпоследовательности, такие как $[1, 1, 3]$, $[1, 2]$ и $[2, 1, 1, 3]$, имеют мажоритарные элементы, а $[1, 2, 1, 3]$ не является хорошей, так как $[2, 1, 3]$ не имеет мажоритарного элемента.

Дана строка, состоящая из $1, 2, 3$ и $?$. Посчитайте количество способов сформировать хорошую последовательность из $1, 2$ и $3$, заменив каждый символ $?$ на $1, 2$ или $3$. Выведите ответ по модулю $10^9 + 7$.

Входные данные

Первая строка содержит целое число $N$ ($3 \le N \le 200$), длину строки. Вторая строка содержит строку длины $N$, состоящую из $1, 2, 3$ и $?$.

Выходные данные

Выведите остаток от деления ответа на $10^9 + 7$.

Подзадачи

• (10 баллов) $N \le 10$, входные данные содержат только $?$.
• (20 баллов) $N \le 25$, входные данные содержат только $?$.
• (40 баллов) $N \le 60$.
• (30 баллов) Без дополнительных ограничений.

Примеры

Пример 1

3
???

21

Пример 2

3
12?

2

Пример 3

4
1?11

3

Пример 4

5
12213

0

Пример 5

10
???1??????

1735

Примечание

Для первого примера единственные массивы (из $3^3 = 27$ возможных), которые не являются хорошими, — это $[1, 2, 3]$ и его перестановки, поэтому ответ равен $27 - 3! = 21$.

Для второго примера $[1, 2, 1]$ и $[1, 2, 2]$ являются хорошими, но $[1, 2, 3]$ — нет.

Для третьего примера $[1, 1, 1, 1]$, $[1, 2, 1, 1]$ и $[1, 3, 1, 1]$ являются хорошими.

Для четвертого примера, так как $[1, 2, 2, 1, 3]$ не является хорошей, ответ равен нулю.