На дворе 2075 год. Разбирая свои архивы, вы вновь обнаружили коллекцию значков с региональных соревнований ICPC 2025 года, которые изначально распространялись организацией Universal Cup.

Полный набор значков 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$).

Вторая строка содержит строку $S$ длины $4n$, состоящую из символов u, c, p и ?.

Выходные данные

Выведите количество способов заменить каждый символ ? в $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