分数: 300 点
问题陈述
我们有 N 卡片从左到右排列成一排。 我们将在之间写一个整数 每张卡片上都有 1 和 K (含),这些卡片最初是空白的。
给出的是 K 限制编号 1 通过 K。
限制 i 由一个字符组成 c_i 和一个整数 k_i。
如果 c_i is L, k_i该行左起第一张牌必须是 最左边
我们写的 卡 i。
如果 c_i is R, k_i该行左起第一张牌必须是 最右边 卡 i.
请注意,对于每个整数 i 来自 1 通过 K,必须至少有一张我们写的卡片 i.
求下列卡片上写整数的方法数 K 限制,模数 998244353.
约束
- 1 \leq N,K \leq 1000
- c_i is
LorR. - 1 \leq k_i \leq N
- k_i \neq k_j if i \neq j.
输入
输入由标准输入按以下格式给出:
N K c_1 k_1 \vdots c_K 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.