题目描述

有 $N$ 张卡片从左到右排列。每张卡片上可以写一个 $1$ 到 $K$ 之间的整数。开始时，所有卡片上都没有写整数。

现在给出 $K$ 个编号为 $1$ 到 $K$ 的限制条件。第 $i$ 个限制由一个字符 $c_i$ 和一个整数 $k_i$ 组成。如果 $c_i$ 是 L，那么所有写有 $i$ 的卡片中，最靠左的一张必须是第 $k_i$ 张卡片（从左到右编号）。如果 $c_i$ 是 R，那么所有写有 $i$ 的卡片中，最靠右的一张必须是第 $k_i$ 张卡片。

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

请计算满足上述 $K$ 个限制条件的卡片写数方案数，并对 $998244353$ 取模。

输入格式

输入从标准输入读入，格式如下：

$N$ $K$
$c_1$ $k_1$
$\vdots$
$c_K$ $k_K$

输出格式

输出满足题目中 $K$ 个限制条件的卡片写数方案数，对 $998244353$ 取模。

样例 1

输入

3 2
L 1
R 2

输出

1

样例 2

输入

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

输出

343921442

说明/提示

限制

• $1 \leq N, K \leq 1000$
• $c_i$ 是 L 或 R 之一
• $1 \leq k_i \leq N$
• 若 $i \neq j$，则 $k_i \neq k_j$

样例解释 1

• 只有一种写法可以满足两个限制条件：在第 $1$ 张卡片上写 $1$，第 $2$ 张卡片上写 $2$，第 $3$ 张卡片上写 $1$。

样例解释 2

• 不要忘记对 $998244353$ 取模。

由 ChatGPT 4.1 翻译