Det är år 2075. När du organiserade dina arkiv återupptäckte du en samling märken från de regionala ICPC-tävlingarna 2025, som ursprungligen delades ut av organisationen Universal Cup.

Ett komplett set med UCup-märken.

I det här problemet betraktar vi dock bara en delmängd av tre färger.

Dina märken finns endast i tre distinkta färger: Ultramarin (u), Karmosin (c) och Snäckskalsblå (p). Ett komplett souvenirpaket definieras som fyra märken som förekommer i den exakta ordningen: Ultramarin, sedan Karmosin, sedan Ultramarin och sedan Snäckskalsblå (ucup).

Din samling består av $4n$ märken placerade på en rad. Du minns tydligt att denna placering år 2025 utgjorde en perfekt omgång:

• Sekvensen kunde delas upp i $n$ disjunkta delsekvenser (det vill säga genom att använda varje märke i exakt en delsekvens), så att varje delsekvens bildade ett komplett souvenirpaket (ucup).

Under de senaste 50 åren har dock vissa märken bleknat, vilket gör det omöjligt att urskilja deras färger. Dessa positioner representeras av ?.

Givet det nuvarande tillståndet för märkessekvensen $S$, beräkna antalet sätt att återställa de bleknade färgerna (?) till ett av u, c eller p, så att den resulterande sekvensen blir en perfekt omgång. Eftersom svaret kan vara stort ska det skrivas ut modulo $998\,244\,353$.

Observera att en delsekvens kan bildas från en sträng genom att ta bort noll eller fler tecken utan att ändra ordningen på de återstående tecknen. Till exempel är ucp, c och ucup delsekvenser av strängen ucup, medan uucp inte är en delsekvens av strängen ucup.

Indata

Den första raden innehåller ett heltal $n$ ($1 \le n \le 50$).

Den andra raden innehåller en sträng $S$ med längden $4n$ som består av tecknen u, c, p och ?.

Utdata

Skriv ut antalet sätt att ersätta varje ? i $S$ med ett av u, c eller p, så att den resulterande strängen representerar en perfekt omgång, modulo $998\,244\,353$.

Exempel

Indata 1

1
????

Utdata 1

1

Indata 2

1
ucup

Utdata 2

1

Indata 3

1
uucp

Utdata 3

0

Indata 4

1
uu?u

Utdata 4

0

Indata 5

2
????????

Utdata 5

11

Indata 6

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

Utdata 6

437