A - LR Constraints 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 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 で割ったあまりを出力せよ。

入力例 1

3 2
L 1
R 2

出力例 1

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

入力例 2

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

出力例 2

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

Score : 300 points

Problem Statement

We have N cards arranged in a row from left to right. We will write an integer between 1 and K (inclusive) on each of these cards, which are initially blank.

Given are K restrictions numbered 1 through K. Restriction i is composed of a character c_i and an integer k_i. If c_i is L, the k_i-th card from the left in the row must be the leftmost card on which we write i. If c_i is R, the k_i-th card from the left in the row must be the rightmost card on which we write i.

Note that for each integer i from 1 through K, there must be at least one card on which we write i.

Find the number of ways to write integers on the cards under the K restrictions, modulo 998244353.

Constraints

  • 1 \leq N,K \leq 1000
  • c_i is L or R.
  • 1 \leq k_i \leq N
  • k_i \neq k_j if i \neq j.

Input

Input is given from Standard Input in the following format:

N K
c_1 k_1
\vdots
c_K k_K

Output

Find the number of ways to write integers on the cards under the K restrictions in the Problem Statement, modulo 998244353.

Sample Input 1

3 2
L 1
R 2

Sample Output 1

1
  • The only way to meet the two restrictions is to write 1, 2, 1 from left to right on the three cards.

Sample Input 2

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

Sample Output 2

343921442
  • Be sure to find the count modulo 998244353.