時は 2075 年。アーカイブを整理していたあなたは、もともと Universal Cup 運営組織によって配布された 2025 年 ICPC 地区大会のバッジのコレクションを再発見しました。

完全な UCup バッジセット。

ただし、この問題では 3 色の部分集合のみを考えます。

あなたのバッジは、ウルトラマリン（u）、クリムゾン（c）、ペリウィンクル（p）の 3 種類の色しかありません。完全な記念品パックとは、ウルトラマリン、次にクリムゾン、次にウルトラマリン、そしてペリウィンクル（ucup）という正確な順序で並んだ 4 つのバッジとして定義されます。

あなたのコレクションは、一列に並んだ $4n$ 個のバッジからなります。あなたは 2025 年当時、この並びが完璧なバッチであったことを鮮明に覚えています：

• この列は、互いに素な $n$ 個の部分列に分割でき（すなわち、各バッジをちょうど 1 つの部分列で使用し）、各部分列が完全な記念品パック（ucup）を形成していた。

しかし、過去 50 年の間にいくつかのバッジが色あせてしまい、その色が判別できなくなってしまいました。これらの位置は ? で表されます。

バッジの列の現在の状態 $S$ が与えられたとき、色あせた位置（?）を u、c、p のいずれかに復元して、結果として得られる列が完璧なバッチになるような方法の数を求めてください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

なお、部分列とは、残りの文字の順序を変えることなく文字列から 0 個以上の文字を削除して得られる列のことです。たとえば、ucp、c、ucup は文字列 ucup の部分列ですが、uucp は文字列 ucup の部分列ではありません。

入力

1 行目には整数 $n$（$1 \le n \le 50$）が与えられます。

2 行目には文字 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