配点 : 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 时不要忘记求余数。