Det er år 2075. Mens du organiserte arkivene dine, gjenoppdaget du en samling merker fra de regionale ICPC-konkurransene i 2025, opprinnelig delt ut av organisasjonen Universal Cup.

Et komplett sett med UCup-merker.

I denne oppgaven ser vi imidlertid bare på en delmengde av tre farger.

Merkene dine kommer kun i tre forskjellige farger: Ultramarin (u), Karmosin (c) og Gravmyrtblå (p). En komplett suvenirpakke er definert som fire merker som opptrer i den nøyaktige rekkefølgen: Ultramarin, deretter Karmosin, deretter Ultramarin og deretter Gravmyrtblå (ucup).

Samlingen din består av $4n$ merker stilt opp på en rad. Du husker tydelig at i 2025 var denne oppstillingen en perfekt pulje:

• Sekvensen kunne deles inn i $n$ disjunkte delsekvenser (det vil si ved å bruke hvert merke i nøyaktig én delsekvens), slik at hver delsekvens dannet en komplett suvenirpakke (ucup).

I løpet av de siste 50 årene har imidlertid noen merker falmet, slik at fargene deres ikke lenger kan skilles fra hverandre. Disse posisjonene er representert ved ?.

Gitt den nåværende tilstanden til merkesekvensen $S$, beregn antall måter å gjenopprette de falmede fargene (?) til en av u, c eller p på, slik at den resulterende sekvensen blir en perfekt pulje. Siden svaret kan være stort, skal du skrive det ut modulo $998\,244\,353$.

Merk at en delsekvens kan utledes fra en streng ved å fjerne null eller flere tegn uten å endre rekkefølgen på de gjenværende tegnene. For eksempel er ucp, c og ucup delsekvenser av strengen ucup, mens uucp ikke er en delsekvens av strengen ucup.

Inndata

Den første linjen inneholder et heltall $n$ ($1 \le n \le 50$).

Den andre linjen inneholder en streng $S$ med lengde $4n$ bestående av tegnene u, c, p og ?.

Utdata

Skriv ut antall måter å erstatte hvert ? i $S$ med en av u, c eller p på, slik at den resulterende strengen representerer en perfekt pulje, regnet modulo $998\,244\,353$.

Eksempler

Inndata 1

1
????

Utdata 1

1

Inndata 2

1
ucup

Utdata 2

1

Inndata 3

1
uucp

Utdata 3

0

Inndata 4

1
uu?u

Utdata 4

0

Inndata 5

2
????????

Utdata 5

11

Inndata 6

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

Utdata 6

437