Wir schreiben das Jahr 2075. Beim Ordnen Ihrer Archive haben Sie eine Sammlung von Abzeichen der regionalen ICPC-Wettbewerbe aus dem Jahr 2025 wiederentdeckt, die ursprünglich von der Organisation Universal Cup verteilt wurden.

Ein komplettes UCup-Abzeichen-Set.

In diesem Problem betrachten wir jedoch nur eine Teilmenge von drei Farben.

Ihre Abzeichen gibt es nur in drei verschiedenen Farben: Ultramarin (u), Karmesinrot (c) und Immergrünblau (p). Ein vollständiges Souvenirpaket ist definiert als vier Abzeichen, die in genau dieser Reihenfolge erscheinen: Ultramarin, dann Karmesinrot, dann Ultramarin, dann Immergrünblau (ucup).

Ihre Sammlung besteht aus $4n$ Abzeichen, die in einer Reihe angeordnet sind. Sie erinnern sich noch lebhaft daran, dass diese Anordnung im Jahr 2025 eine perfekte Charge war:

• Die Folge konnte in $n$ disjunkte Teilfolgen zerlegt werden (d. h. jedes Abzeichen wurde in genau einer Teilfolge verwendet), sodass jede Teilfolge ein vollständiges Souvenirpaket (ucup) bildete.

Im Laufe der letzten 50 Jahre sind jedoch einige Abzeichen verblasst, sodass ihre Farben nicht mehr zu unterscheiden sind. Diese Positionen werden durch ? dargestellt.

Berechnen Sie ausgehend vom aktuellen Zustand der Abzeichenfolge $S$ die Anzahl der Möglichkeiten, die verblassten Farben (?) durch u, c oder p zu ersetzen, sodass die resultierende Folge eine perfekte Charge ist. Da die Antwort groß sein kann, geben Sie sie modulo $998\,244\,353$ aus.

Beachten Sie, dass eine Teilfolge aus einer Zeichenkette abgeleitet werden kann, indem null oder mehr Zeichen entfernt werden, ohne die Reihenfolge der verbleibenden Zeichen zu ändern. Beispielsweise sind ucp, c und ucup Teilfolgen der Zeichenkette ucup, während uucp keine Teilfolge der Zeichenkette ucup ist.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 50$).

Die zweite Zeile enthält eine Zeichenkette $S$ der Länge $4n$, die aus den Zeichen u, c, p und ? besteht.

Ausgabe

Geben Sie die Anzahl der Möglichkeiten aus, jedes ? in $S$ durch eines der Zeichen u, c oder p zu ersetzen, sodass die resultierende Zeichenkette eine perfekte Charge darstellt, modulo $998\,244\,353$.

Beispiele

Eingabe 1

1
????

Ausgabe 1

1

Eingabe 2

1
ucup

Ausgabe 2

1

Eingabe 3

1
uucp

Ausgabe 3

0

Eingabe 4

1
uu?u

Ausgabe 4

0

Eingabe 5

2
????????

Ausgabe 5

11

Eingabe 6

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

Ausgabe 6

437