問題文

円周上に $2N$ 個の点が等間隔にあり、時計回りに $1,2, \cdots ,2N$ と番号付けられています。
また、文字列 $S$ の $i$ 文字目が R の場合は点 $i$ は赤色に、 B の場合は青色に塗られています。

ここで、円周上の $2N$ 個の点を $N$ 個のペアに分ける方法で以下を満たすものを いい分け方 と定義します。

• $N$ 個全てのペアについて、ペアが含む $2$ つの点の色は同じである。
• $2N$ 個全ての点について、その点を含むペアはちょうど $1$ 個である。

• 全てのペアに対してそのペアの $2$ つの点を結ぶ線分を引く。この操作によってできた $N$ 本の線分から $2$ 本の線分を選ぶ方法で、選んだ $2$ 本が交わるような通り数。

いい分け方に対するスコアの期待値を求めてください。与えられる入力において、いい分け方が存在することが保障されます。
ここで、答えが互いに素である $2$ つの $0$ 以上の整数 $P,Q$ を用いて $\frac{P}{Q}$ と表現可能であることと、 $R \times Q \equiv P (\mathrm{mod}\ 998244353)$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ が一意に定まることが証明できるので $R$ を出力してください。

なお、この問題において、 $S$ は以下のように与えられます。

• 正整数 $X$ と文字 $C_1,C_2, \cdots , C_X$ と数字 $V_1,V_2, \cdots ,V_X$ が与えられる。 $S_i$ は $C_i$ を $V_i$ 文字並べたものとして、 $S$ は $S_1,S_2 , \cdots ,S_X$ をこの順で並べたものである。

入力

$N\ \ X$
$C_1\ \ V_1$
$C_2\ \ V_2$
$\vdots$
$C_X\ \ V_X$

• $1 \leq N \leq 499122176 = \frac{998244353-1}{2}$
• $1 \leq X \leq 4 \times 10^5$
• $C_i$ は R または B $\left( 1 \leq i \leq X \right)$
• $1 \leq V_i \leq 2N$ $\left( 1 \leq i \leq X \right)$
• $V_1 + V_2 + \cdots + V_X = 2N$
• $N,X,V_i$ は整数
• いい分け方が存在する

出力

問題文に従って求めた $R$ を出力し、最後に改行してください。

サンプル

2 4
R 1
B 1
R 1
B 1

1

4 5
B 4
R 1
B 1
B 1
R 1

798595485

24 19
B 3
R 1
B 2
R 1
B 1
R 3
B 2
R 1
B 4
R 1
B 1
R 2
B 1
R 7
B 7
R 2
B 6
R 2
B 1

865923553