题目描述

小高和小李有 $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$

$\vdots$

$c_K$ $k_K$

输出格式

输出一个整数，表示满足所有限制条件的写数字方法数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 2
L 1
R 2

输出 #1

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

说明/提示

样例 1 解释

唯一满足两个限制条件的方法是从左到右在三张卡片上写 $1, 2, 1$。

样例 2 解释

请确保对 $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$