Un élément majoritaire d'une séquence d'entiers positifs est un nombre égal à au moins la moitié de ses éléments.

Une séquence est dite bonne si tous ses segments contigus non vides possèdent au moins un élément majoritaire. Par exemple, $[1, 2, 1, 1, 3]$ est bonne, car des segments tels que $[1, 1, 3]$, $[1, 2]$ et $[2, 1, 1, 3]$ possèdent tous des éléments majoritaires, mais $[1, 2, 1, 3]$ n'est pas bonne car $[2, 1, 3]$ ne possède pas d'élément majoritaire.

Étant donné une chaîne composée de 1, 2, 3 et ?, comptez le nombre de façons de former une bonne séquence de 1, 2 et 3 en remplaçant chaque ? par l'un des chiffres 1, 2 ou 3. Donnez le résultat modulo $10^9 + 7$.

Entrée

La première ligne contient un entier $N$ ($3 \le N \le 200$), la longueur de la chaîne. La deuxième ligne contient une chaîne de longueur $N$, composée de 1, 2, 3 et ?.

Sortie

Affichez le reste de la division du résultat par $10^9 + 7$.

Sous-tâches

• (10 points) $N \le 10$, l'entrée ne contient que des ?.
• (20 points) $N \le 25$, l'entrée ne contient que des ?.
• (40 points) $N \le 60$.
• (30 points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

3
???

Sortie 1

21

Entrée 2

3
12?

Sortie 2

2

Entrée 3

4
1?11

Sortie 3

3

Entrée 4

5
12213

Sortie 4

0

Entrée 5

10
???1??????

Sortie 5

1735

Remarque

Pour le premier exemple, les seuls tableaux (parmi $3^3 = 27$ possibles) qui ne sont pas bons sont $[1, 2, 3]$ et ses permutations, donc la réponse est $27 - 3! = 21$.

Pour le deuxième exemple, $[1, 2, 1]$ et $[1, 2, 2]$ sont bons, mais pas $[1, 2, 3]$.

Pour le troisième exemple, $[1, 1, 1, 1]$, $[1, 2, 1, 1]$ et $[1, 3, 1, 1]$ sont tous bons.

Pour le quatrième exemple, puisque $[1, 2, 2, 1, 3]$ n'est pas bonne, la réponse est zéro.