← 返回题目列表

AtCoder · pakencamp_2024_day1_m

M. 强弦

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

配点 : 500 点

問題文

由大写字母组成的长度,满足以下所有条件: 2N 字符串 使用 S 可能的事物数量是 除以 998244353 求余数。

  • 没有相邻的字符相同。
  • 第一个 N 字母和最后一个 N 字符不匹配。具体来说, S_1 \neq S_{N+1}, S_2 \neq S_{N+2}, \ldots, S_N \neq S_{2N} 为真。
  • 1 以上 K 的整数 i , 满足 S_{A_i}=C_i 满意。

制約

  • 1 \leq N \leq 10^9
  • 0 \leq K \leq 10^5
  • 1 \leq A_i \leq 2N (1 \leq i \leq K)
  • A_i < A_{i+1} (1 \leq i \leq K-1)
  • C_i (1 \leq i \leq K) 均为大写字母
  • N, K, A_i (1 \leq i \leq K) 均为整数 像

入力

输入是按以下格式从标准输入给出的。

N K
A_1 C_1
A_2 C_2
\vdots
A_K C_K

出力

打印答案。


入力例 1

2 2
1 T
4 A

出力例 1

600

例如, TUNA 这样的字符串满足条件,但是 像 TATA , TTTA 这样的字符串不满足条件。


入力例 2

3 4
1 B
2 E
3 E
4 T

出力例 2

0

无论你在其余部分输入什么字符 2 信和 3 由于字母相同,因此永远不会满足条件。 除以


入力例 3

1 0

出力例 3

650

入力例 4

6 2
4 O
7 S

出力例 4

606171726

答案 对于 998244353 时不要忘记求余数。