而家係 2075 年。喺整理檔案嗰陣，你重新發現咗 2025 年 ICPC 區域賽嘅一套襟章，呢啲襟章最初係由 Universal Cup 組織派發嘅。

一套完整嘅 UCup 襟章。

不過，喺呢題入面，我哋只考慮其中三種顏色嘅子集。

你嘅襟章只有三種唔同嘅顏色：群青色（Ultramarine，用 u 代表）、緋紅色（Crimson，用 c 代表）同埋長春花藍色（Periwinkle，用 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$）。

第二行包含一個長度為 $4n$ 嘅字串 $S$，由字符 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