问题陈述

有 $N$ 张卡片按从左到右排成一行。我们将在这些卡片上写一个介于 $1$ 和 $K$（含）之间的整数，初始时卡片为空白。

给定的是 $K$ 个约束，编号为 $1$ 到 $K$。约束 $i$ 由字符 $c_i$ 和整数 $k_i$ 组成。如果 $c_i$ 是 L，则行中第 $k_i$ 张卡片必须是我们写 $i$ 的最左边的卡片。如果 $c_i$ 是 R，则行中第 $k_i$ 张卡片必须是我们写 $i$ 的最右边的卡片。

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

求在 $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$

输出

求在问题陈述下，在卡片上写整数的方法数，对 $998244353$ 取模。

示例输入 1

3 2
L 1
R 2

示例输出 1

1

• 满足两个约束的唯一方式是从左到右在三张卡片上写 $1, 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

示例输出 2

343921442

• 确保对 $998244353$ 取模后计算计数。