問題文

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

入力例 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 で割った余りを求めることを忘れないでください。