È l'anno 2075. Mentre riordinavi i tuoi archivi, hai riscoperto una collezione di spille delle gare regionali ICPC 2025, originariamente distribuite dall'organizzazione Universal Cup.

Un set completo di spille UCup.

In questo problema, tuttavia, consideriamo solo un sottoinsieme di tre colori.

Le tue spille sono disponibili solo in tre colori distinti: Oltremare (u), Cremisi (c) e Pervinca (p). Un pacchetto souvenir completo è definito come quattro spille che compaiono nell'ordine esatto: Oltremare, poi Cremisi, poi Oltremare, poi Pervinca (ucup).

La tua collezione è composta da $4n$ spille disposte in fila. Ricordi vividamente che nel 2025 questa disposizione costituiva un lotto perfetto:

• La sequenza poteva essere partizionata in $n$ sottosequenze disgiunte (cioè utilizzando ogni spilla in esattamente una sottosequenza), in modo tale che ogni sottosequenza formasse un pacchetto souvenir completo (ucup).

Tuttavia, negli ultimi 50 anni, alcune spille si sono sbiadite, rendendo i loro colori indistinguibili. Queste posizioni sono rappresentate da ?.

Dato lo stato attuale della sequenza di spille $S$, calcola il numero di modi per ripristinare i colori sbiaditi (?) in uno tra u, c o p, in modo che la sequenza risultante sia un lotto perfetto. Poiché la risposta può essere grande, stampala modulo $998\,244\,353$.

Si noti che una sottosequenza può essere ottenuta da una stringa rimuovendo zero o più caratteri senza modificare l'ordine dei caratteri rimanenti. Ad esempio, ucp, c e ucup sono sottosequenze della stringa ucup, mentre uucp non è una sottosequenza della stringa ucup.

Input

La prima riga contiene un intero $n$ ($1 \le n \le 50$).

La seconda riga contiene una stringa $S$ di lunghezza $4n$ composta dai caratteri u, c, p e ?.

Output

Stampa il numero di modi per sostituire ogni ? in $S$ con uno tra u, c o p, in modo che la stringa risultante rappresenti un lotto perfetto, modulo $998\,244\,353$.

Esempi

Input 1

1
????

Output 1

1

Input 2

1
ucup

Output 2

1

Input 3

1
uucp

Output 3

0

Input 4

1
uu?u

Output 4

0

Input 5

2
????????

Output 5

11

Input 6

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

Output 6

437