题目描述

小高和小李有$N$张卡片排成一排，从左到右排列。他们将在每张卡片上写一个$1$到$K$之间的整数（包括$1$和$K$）。

给定$K$个限制条件，每个条件由一个字符$c_i$和一个整数$k_i$组成。如果$c_i$是'L'，则第$k_i$张卡片（从左数）必须是写有数字$i$的最左边的卡片。如果$c_i$是'R'，则第$k_i$张卡片必须是写有数字$i$的最右边的卡片。

注意，对于$1$到$K$之间的每个整数i，必须至少有一张卡片写有$i$。

请计算在满足这$K$个限制条件下，有多少种在卡片上写数字的方法。答案对998244353取模。

输入格式

输入从标准输入中给出，格式如下：

$N$ $K$

$c_1$ $k_1$

$c_2$ $k_2$

$\cdots$

$c_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说明】
唯一满足两个限制条件的方法是从左到右在三张卡片上写1, 2, 1。
【样例2说明】
请确保对998244353取模后输出结果。

数据范围

• $1 ≤ N, K ≤ 1000$
• $c_i$ 是 'L' 或 'R'
• $1 ≤ k_i ≤ N$
• 如果 $i ≠ j$，则 $k_i ≠ k_j$。

来源

• AtCoder ARC124A