题目描述

$N$ 枚のカードが左から右に並んでいます。 各カードに $1$ 以上 $K$ 以下の整数を書き込みます。はじめ、どのカードにも整数は書かれていません。

$1$ から $K$ の番号がついた $K$ 個の制約が与えられます。 制約 $i$ は文字 $c_i$ と整数 $k_i$ からなります。 $c_i$ が L ならば、$i$ が書かれたカードのうち最も 左 にあるものは $N$ 枚のカードのうち左から $k_i$ 番目である必要があります。$c_i$ が R ならば、$i$ が書かれたカードのうち最も 右 にあるものは $N$ 枚のカードのうち左から $k_i$ 番目である必要があります。

$1$ 以上 $K$ 以下の各整数 $i$ について、$i$ が書かれたカードが少なくとも $1$ つ存在する必要があることに注意してください。

上記の $K$ 個の制約をすべて満たすようなカードへの整数の書き込み方の個数を $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $c_1$ $k_1$ $\vdots$ $c_K$ $k_K$

输出格式

問題文中の $K$ 個の制約をすべて満たすようなカードへの整数の書き込み方の個数を $998244353$ で割ったあまりを出力せよ。

3 2
L 1
R 2

1

30 10
R 6
R 8
R 7
R 25
L 26
L 13
R 14
L 11
L 23
R 30

343921442

提示

制約

• $1\ \leq\ N,K\ \leq\ 1000$
• $c_i$ は L, R のいずれか
• $1\ \leq\ k_i\ \leq\ N$
• $i\ \neq\ j$ ならば $k_i\ \neq\ k_j$

Sample Explanation 1

- 左から $1$ 番目のカードに $1$ を、$2$ 番目のカードに $2$ を、$3$ 番目のカードに $1$ を書き込むのが $2$ つの制約を満たすような唯一の書き込み方です。

Sample Explanation 2

- $998244353$ で割ったあまりを求めるのを忘れずに。