配点 : $300$ 点

問題文

$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$ で割ったあまりを求めてください。

制約

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

入力

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

$N$ $K$

$c_1$ $k_1$

$\vdots$

$c_K$ $k_K$

出力

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

3 2
L 1
R 2

1

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

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

343921442

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