Jest rok 2075. Podczas porządkowania swoich archiwów odkryłeś na nowo kolekcję przypinek z zawodów regionalnych ICPC 2025, pierwotnie rozdanych przez organizację Universal Cup.

Kompletny zestaw przypinek UCup.

W tym zadaniu rozważamy jednak tylko podzbiór trzech kolorów.

Twoje przypinki występują wyłącznie w trzech różnych kolorach: ultramarynowym (u), karmazynowym (c) oraz barwinkowym (p). Kompletny pakiet pamiątkowy definiujemy jako cztery przypinki występujące w dokładnej kolejności: ultramarynowa, następnie karmazynowa, potem ultramarynowa, a na końcu barwinkowa (ucup).

Twoja kolekcja składa się z $4n$ przypinek ułożonych w rzędzie. Doskonale pamiętasz, że w 2025 roku to ułożenie stanowiło idealną partię:

• Ciąg ten można było podzielić na $n$ rozłącznych podciągów (tj. używając każdej przypinki w dokładnie jednym podciągu) w taki sposób, że każdy podciąg tworzył kompletny pakiet pamiątkowy (ucup).

Jednak przez ostatnie 50 lat niektóre przypinki wyblakły, przez co ich kolory stały się nie do odróżnienia. Pozycje te są reprezentowane przez znak ?.

Mając dany obecny stan ciągu przypinek $S$, oblicz liczbę sposobów odtworzenia wyblakłych kolorów (?) jako jednego ze znaków u, c lub p tak, aby otrzymany ciąg był idealną partią. Ponieważ odpowiedź może być duża, wypisz ją modulo $998\,244\,353$.

Zauważ, że podciąg można uzyskać z napisu poprzez usunięcie zera lub więcej znaków bez zmiany kolejności pozostałych znaków. Na przykład ucp, c oraz ucup są podciągami napisu ucup, natomiast uucp nie jest podciągiem napisu ucup.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 50$).

Drugi wiersz zawiera napis $S$ o długości $4n$, składający się ze znaków u, c, p oraz ?.

Wyjście

Wypisz liczbę sposobów zastąpienia każdego znaku ? w $S$ jednym ze znaków u, c lub p tak, aby wynikowy napis reprezentował idealną partię, modulo $998\,244\,353$.

Przykłady

Wejście 1

1
????

Wyjście 1

1

Wejście 2

1
ucup

Wyjście 2

1

Wejście 3

1
uucp

Wyjście 3

0

Wejście 4

1
uu?u

Wyjście 4

0

Wejście 5

2
????????

Wyjście 5

11

Wejście 6

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

Wyjście 6

437