← 返回题目列表

AtCoder · arc124_a

A. LR 约束

中文机器翻译题面 查看原题

分数: 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 L or R.
  • 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.