Subarray Majority

Un elemento mayoritario de una secuencia de enteros positivos es un número igual a al menos la mitad de sus elementos.

Llamamos a una secuencia buena si todos sus segmentos contiguos no vacíos tienen al menos un elemento mayoritario. Por ejemplo, $[1, 2, 1, 1, 3]$ es buena, ya que segmentos como $[1, 1, 3]$, $[1, 2]$ y $[2, 1, 1, 3]$ tienen elementos mayoritarios, pero $[1, 2, 1, 3]$ no es buena porque $[2, 1, 3]$ no tiene un elemento mayoritario.

Dada una cadena que consiste en 1, 2, 3 y ?, cuente el número de formas de formar una secuencia buena de 1, 2 y 3 cambiando cada ? por uno de los números 1, 2 o 3. Imprima la respuesta módulo $10^9 + 7$.

Entrada

La primera línea contiene un entero $N$ ($3 \le N \le 200$), la longitud de la cadena. La segunda línea contiene una cadena de longitud $N$, que consiste en 1, 2, 3 y ?.

Salida

Imprima el resto de la división de la respuesta por $10^9 + 7$.

Puntuación

• (10 puntos) $N \le 10$, la entrada contiene solo ?'s.
• (20 puntos) $N \le 25$, la entrada contiene solo ?'s.
• (40 puntos) $N \le 60$.
• (30 puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

3
???

Salida 1

21

Entrada 2

3
12?

Salida 2

2

Entrada 3

4
1?11

Salida 3

3

Entrada 4

5
12213

Salida 4

0

Entrada 5

10
???1??????

Salida 5

1735

Nota

Para el primer ejemplo, los únicos arreglos (de $3^3 = 27$ posibles) que no son buenos son $[1, 2, 3]$ y sus permutaciones, por lo que la respuesta es $27 - 3! = 21$.

Para el segundo ejemplo, $[1, 2, 1]$ y $[1, 2, 2]$ son buenos, pero $[1, 2, 3]$ no lo es.

Para el tercer ejemplo, $[1, 1, 1, 1]$, $[1, 2, 1, 1]$ y $[1, 3, 1, 1]$ son todos buenos.

Para el cuarto ejemplo, dado que $[1, 2, 2, 1, 3]$ no es buena, la respuesta es cero.