現在是 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