Надворі 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