On vuosi 2075. Järjestellessäsi arkistojasi löysit uudelleen kokoelman vuoden 2025 ICPC-aluekilpailujen pinssejä, jotka Universal Cup -järjestö alun perin jakoi.

Täydellinen UCup-pinssisarja.

Tässä tehtävässä tarkastelemme kuitenkin vain kolmen värin osajoukkoa.

Pinssejäsi on vain kolmea eri väriä: ultramariini (u), karmiininpunainen (c) ja talvio (p). Täydellinen matkamuistopakkaus määritellään neljäksi pinssiksi, jotka esiintyvät täsmälleen järjestyksessä: ultramariini, sitten karmiininpunainen, sitten ultramariini ja sitten talvio (ucup).

Kokoelmasi koostuu $4n$ pinssistä, jotka on järjestetty riviin. Muistat elävästi, että vuonna 2025 tämä järjestys oli täydellinen erä:

• Jono voitiin osittaa $n$ erilliseen osajonoon (eli käyttäen jokaista pinssiä täsmälleen yhdessä osajonossa) siten, että jokainen osajono muodosti täydellisen matkamuistopakkauksen (ucup).

Viimeisten 50 vuoden aikana jotkin pinssit ovat kuitenkin haalistuneet, minkä vuoksi niiden värejä ei voi enää erottaa toisistaan. Näitä kohtia merkitään merkillä ?.

Annettuna pinssijonon nykyinen tila $S$, laske tapojen lukumäärä palauttaa haalistuneet värit (?) joksikin merkeistä u, c tai p siten, että tuloksena oleva jono on täydellinen erä. Koska vastaus voi olla suuri, tulosta se modulo $998\,244\,353$.

Huomaa, että osajono voidaan muodostaa merkkijonosta poistamalla nolla tai useampia merkkejä muuttamatta jäljelle jäävien merkkien järjestystä. Esimerkiksi ucp, c ja ucup ovat merkkijonon ucup osajonoja, kun taas uucp ei ole merkkijonon ucup osajono.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 50$).

Toinen rivi sisältää pituudeltaan $4n$ olevan merkkijonon $S$, joka koostuu merkeistä u, c, p ja ?.

Tuloste

Tulosta tapojen lukumäärä korvata jokainen ? merkkijonossa $S$ jollakin merkeistä u, c tai p siten, että tuloksena oleva merkkijono edustaa täydellistä erää, modulo $998\,244\,353$.

Esimerkit

Syöte 1

1
????

Tuloste 1

1

Syöte 2

1
ucup

Tuloste 2

1

Syöte 3

1
uucp

Tuloste 3

0

Syöte 4

1
uu?u

Tuloste 4

0

Syöte 5

2
????????

Tuloste 5

11

Syöte 6

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

Tuloste 6

437