Қазір 2075 жыл. Архивтеріңізді ретке келтіріп жүріп, сіз бастапқыда Universal Cup ұйымы таратқан 2025 жылғы ICPC аймақтық жарыстарының төсбелгілер топтамасын қайта таптыңыз.

Толық UCup төсбелгілер жиынтығы.

Дегенмен, бұл есепте біз тек үш түстен тұратын ішкі жиынды қарастырамыз.

Сіздің төсбелгілеріңіз тек үш түрлі түсте кездеседі: ультрамарин (u), қызыл күрең (c) және қабыршақ көк (p). Толық кәдесый жиынтығы дәл мына ретпен келетін төрт төсбелгі ретінде анықталады: ультрамарин, содан кейін қызыл күрең, содан кейін ультрамарин, содан кейін қабыршақ көк (ucup).

Сіздің топтамаңыз бір қатарға тізілген $4n$ төсбелгіден тұрады. 2025 жылы бұл орналасудың мінсіз партия болғаны есіңізде:

• Тізбекті өзара қиылыспайтын $n$ ішкі тізбекке бөлуге болатын еді (яғни, әрбір төсбелгіні дәл бір ішкі тізбекте пайдаланып), сонда әрбір ішкі тізбек толық кәдесый жиынтығын (ucup) құрайтын.

Алайда, соңғы 50 жыл ішінде кейбір төсбелгілердің бояуы оңып, олардың түстерін ажырату мүмкін болмай қалды. Бұл орындар ? таңбасымен белгіленген.

Төсбелгілер тізбегінің ағымдағы күйі $S$ берілген. Алынған тізбек мінсіз партия болатындай етіп, оңып кеткен түстерді (?) u, c немесе p таңбаларының біріне қалпына келтіру тәсілдерінің санын есептеңіз. Жауап үлкен болуы мүмкін болғандықтан, оны $998\,244\,353$ модулі бойынша шығарыңыз.

Ішкі тізбекті жолдан қалған таңбалардың ретін өзгертпей нөл немесе одан көп таңбаны өшіру арқылы алуға болатынын ескеріңіз. Мысалы, ucp, c және ucup — ucup жолының ішкі тізбектері, ал uucp — ucup жолының ішкі тізбегі емес.

Кіріс деректер

Бірінші жолда бір бүтін сан $n$ ($1 \le n \le 50$) берілген.

Екінші жолда u, c, p және ? таңбаларынан тұратын ұзындығы $4n$ болатын $S$ жолы берілген.

Шығыс деректер

Алынған жол мінсіз партияны білдіретіндей етіп, $S$ ішіндегі әрбір ? таңбасын u, c немесе p таңбаларының бірімен алмастыру тәсілдерінің санын $998\,244\,353$ модулі бойынша шығарыңыз.

Мысалдар

Кіріс деректер 1

1
????

Шығыс деректер 1

1

Кіріс деректер 2

1
ucup

Шығыс деректер 2

1

Кіріс деректер 3

1
uucp

Шығыс деректер 3

0

Кіріс деректер 4

1
uu?u

Шығыс деректер 4

0

Кіріс деректер 5

2
????????

Шығыс деректер 5

11

Кіріс деректер 6

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

Шығыс деректер 6

437