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.

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.

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$.

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.

见题面 Input 部分

见题面 Output 部分