AT_pakencamp_2024_day1_m Strong String

求满足以下所有条件的，由英文大写字母组成的长度为 $2N$ 的字符串 $S$ 的个数，并对 $998244353$ 取模。 - 任意相邻的字符都不相同。 - 前 $N$ 个字符与后 $N$ 个字符不完全相同。具体来说，存在至少一个 $i$ 满足 $S_i \neq S_{N+i}$（$1 \leq i \leq N$）。 - 对于 $1$ 到 $K$ 的每一个整数 $i$，有 $S_{A_i} = C_i$。

输入按以下格式从标准输入读入。 > $N\ K\ A_1\ C_1\ A_2\ C_2\ \vdots\ A_K\ C_K$

输出答案。

### 样例解释 1 例如，`TUNA` 这样的字符串满足条件，但 `TATA`、`TTTA` 这样的字符串则不满足条件。 ### 样例解释 2 无论其余部分如何填充，由于第 $2$ 个和第 $3$ 个字符相同，因此无法满足条件。 ### 样例解释 4 不要忘记对 $998244353$ 取模。 ### 数据范围 - $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$）均为整数 由 ChatGPT 5 翻译