Es el año 2075. Mientras organizabas tus archivos, redescubriste una colección de insignias de los concursos regionales de ICPC de 2025, distribuidas originalmente por la organización Universal Cup.

Un juego completo de insignias de UCup.

Sin embargo, en este problema solo consideramos un subconjunto de tres colores.

Tus insignias vienen únicamente en tres colores distintos: Ultramar (u), Carmesí (c) y Bígaro (p). Un paquete de recuerdo completo se define como cuatro insignias que aparecen en el orden exacto: Ultramar, luego Carmesí, luego Ultramar y luego Bígaro (ucup).

Tu colección consta de $4n$ insignias dispuestas en una fila. Recuerdas vívidamente que en 2025 esta disposición era un lote perfecto:

• La secuencia podía particionarse en $n$ subsecuencias disjuntas (es decir, usando cada insignia en exactamente una subsecuencia), de modo que cada subsecuencia formara un paquete de recuerdo completo (ucup).

Sin embargo, durante los últimos 50 años, algunas insignias se han desteñido, haciendo que sus colores sean indistinguibles. Estas posiciones están representadas por ?.

Dado el estado actual de la secuencia de insignias $S$, calcula el número de formas de restaurar los colores desteñidos (?) a uno de u, c o p, de tal manera que la secuencia resultante sea un lote perfecto. Como la respuesta puede ser grande, imprímela módulo $998\,244\,353$.

Ten en cuenta que una subsecuencia se puede obtener de una cadena eliminando cero o más caracteres sin cambiar el orden de los caracteres restantes. Por ejemplo, ucp, c y ucup son subsecuencias de la cadena ucup, mientras que uucp no es una subsecuencia de la cadena ucup.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 50$).

La segunda línea contiene una cadena $S$ de longitud $4n$ formada por los caracteres u, c, p y ?.

Salida

Imprime el número de formas de reemplazar cada ? en $S$ por uno de u, c o p, de modo que la cadena resultante represente un lote perfecto, tomado módulo $998\,244\,353$.

Ejemplos

Entrada 1

1
????

Salida 1

1

Entrada 2

1
ucup

Salida 2

1

Entrada 3

1
uucp

Salida 3

0

Entrada 4

1
uu?u

Salida 4

0

Entrada 5

2
????????

Salida 5

11

Entrada 6

4
u???c???u???p???

Salida 6

437