Árið er 2075. Þegar þú varst að taka til í skjalasafninu þínu fannstu aftur safn af barmmerkjum frá svæðiskeppnum ICPC árið 2025, sem Universal Cup samtökin dreifðu upphaflega.
Heilt sett af UCup barmmerkjum.
Í þessu verkefni skoðum við hins vegar aðeins hlutmengi af þremur litum.
Barmmerkin þín eru aðeins til í þremur ólíkum litum: Últramarínbláum (u), Rauðfjólubláum (c) og Periwinkle-bláum (p). Fullkominn minjagripapakki er skilgreindur sem fjögur barmmerki sem birtast í nákvæmlega þessari röð: Últramarínblátt, síðan Rauðfjólublátt, síðan Últramarínblátt og loks Periwinkle-blátt (ucup).
Safnið þitt samanstendur af $4n$ barmmerkjum sem raðað er í röð. Þú manst skýrt að árið 2025 var þessi uppröðun fullkominn skammtur:
- Rununni mátti skipta í $n$ sundurlausar hlutrunur (þ.e. hvert barmmerki var notað í nákvæmlega einni hlutrunu), þannig að hver hlutruna myndaði fullkominn minjagripapakka (
ucup).
Hins vegar hafa sum barmmerkin upplitast á síðustu 50 árum, þannig að ómögulegt er að greina liti þeirra. Þessar stöður eru táknaðar með ?.
Gefið núverandi ástand barmmerkjarununnar $S$, reiknaðu fjölda leiða til að endurheimta upplituðu litina (?) í einn af u, c eða p, þannig að runan sem fæst sé fullkominn skammtur. Þar sem svarið getur verið stórt skal prenta það módúló $998\,244\,353$.
Athugið að hlutrunu má fá úr streng með því að fjarlægja núll eða fleiri stafi án þess að breyta röð stafanna sem eftir standa. Til dæmis eru ucp, c og ucup hlutrunur strengsins ucup, en uucp er ekki hlutruna strengsins ucup.
Inntak
Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 50$).
Önnur línan inniheldur streng $S$ af lengd $4n$ sem samanstendur af stöfunum u, c, p og ?.
Úttak
Prentið fjölda leiða til að skipta hverju ? í $S$ út fyrir einn af stöfunum u, c eða p, þannig að strengurinn sem fæst tákni fullkominn skammt, tekið módúló $998\,244\,353$.
Dæmi
Inntak 1
1 ????
Úttak 1
1
Inntak 2
1 ucup
Úttak 2
1
Inntak 3
1 uucp
Úttak 3
0
Inntak 4
1 uu?u
Úttak 4
0
Inntak 5
2 ????????
Úttak 5
11
Inntak 6
4 u???c???u???p???
Úttak 6
437