AT_arc124_a [ARC124A] LR Constraints

[problemUrl]: https://atcoder.jp/contests/arc124/tasks/arc124_a $ 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 $ で割ったあまりを出力せよ。

### 制約 - $ 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 $ で割ったあまりを求めるのを忘れずに。