4270: LR Constraints

# LR Constraints ### 内存 1024MB ### 时间 2S ## 题目描述 小高和小李有$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取模。 ## 输入输出样例 ### 输入样例1 ``` 3 2 L 1 R 2 ``` ### 输出样例1 ``` 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 ``` ## 数据范围与提示 【样例1说明】 唯一满足两个限制条件的方法是从左到右在三张卡片上写1, 2, 1。 【样例2说明】 请确保对998244353取模后输出结果。 【数据范围】 - $1 ≤ N, K ≤ 1000$ - $c_i$ 是 '`L`' 或 '`R`' - $1 ≤ k_i ≤ N$ - 如果 $i ≠ j$，则 $k_i ≠ k_j$。 ## 题目来源 ARC124A