Dominantnym elementem ciągu liczb całkowitych dodatnich nazywamy liczbę, która występuje w nim co najmniej tyle razy, ile wynosi połowa długości tego ciągu.

Ciąg nazywamy dobrym, jeśli wszystkie jego niepuste spójne podciągi mają co najmniej jeden dominantny element. Na przykład, $[1, 2, 1, 1, 3]$ jest dobry, ponieważ podciągi takie jak $[1, 1, 3]$, $[1, 2]$ oraz $[2, 1, 1, 3]$ mają dominantne elementy, natomiast $[1, 2, 1, 3]$ nie jest dobry, ponieważ $[2, 1, 3]$ nie posiada dominantnego elementu.

Mając dany ciąg znaków składający się z $1, 2, 3$ oraz $?$, oblicz liczbę sposobów utworzenia dobrego ciągu złożonego z $1, 2$ oraz $3$ poprzez zamianę każdego znaku $?$ na jedną z cyfr $1, 2$ lub $3$. Wynik podaj modulo $10^9 + 7$.

Wejście

Pierwsza linia zawiera liczbę całkowitą $N$ ($3 \le N \le 200$), długość ciągu. Druga linia zawiera ciąg znaków o długości $N$, składający się z $1, 2, 3$ oraz $?$.

Wyjście

Wypisz resztę z dzielenia wyniku przez $10^9 + 7$.

Podzadania

• (10 punktów) $N \le 10$, wejście zawiera tylko znaki $?$.
• (20 punktów) $N \le 25$, wejście zawiera tylko znaki $?$.
• (40 punktów) $N \le 60$.
• (30 punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

3
???

Wyjście 1

21

Wejście 2

3
12?

Wyjście 2

2

Wejście 3

4
1?11

Wyjście 3

3

Wejście 4

5
12213

Wyjście 4

0

Wejście 5

10
???1??????

Wyjście 5

1735

Uwagi

Dla pierwszego przykładu, jedyne tablice (spośród $3^3 = 27$ możliwych), które nie są dobre, to $[1, 2, 3]$ oraz jej permutacje, więc odpowiedź wynosi $27 - 3! = 21$.

Dla drugiego przykładu, $[1, 2, 1]$ oraz $[1, 2, 2]$ są dobre, ale $[1, 2, 3]$ nie jest.

Dla trzeciego przykładu, $[1, 1, 1, 1]$, $[1, 2, 1, 1]$ oraz $[1, 3, 1, 1]$ są dobre.

Dla czwartego przykładu, ponieważ $[1, 2, 2, 1, 3]$ nie jest dobry, odpowiedź wynosi zero.