AT_pakencamp_2024_day1_m Strong String

以下の条件をすべて満たす英大文字からなる長さ $ 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 $ を満たす。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ C_1 $ $ A_2 $ $ C_2 $ $ \vdots $ $ A_K $ $ C_K $

答えを出力せよ。

### Sample Explanation 1 例えば、 `TUNA` のような文字列は条件を満たしますが、 `TATA` , `TTTA` のような文字列は条件を満たしません。 ### Sample Explanation 2 残りの部分にどのような文字を入れても $ 2 $ 文字目と $ 3 $ 文字目が同じであるため、条件を満たすことはありません。 ### Sample Explanation 4 答えを $ 998244353 $ で割った余りを求めることを忘れないでください。 ### Constraints - $ 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 $ ) はすべて整数