题目描述

给定一个由小写英文字母组成的长度为 $N$ 的字符串 $S$。 对 $S$ 恰好进行 $10^{100}$ 次以下操作后，求 $S$ 可能变成的不同字符串的个数，答案对 $998244353$ 取模。

• 选择一个 $1$ 以上 $M$ 以下的整数 $i$，交换 $S$ 的第 $A_i$ 个字符和第 $B_i$ 个字符。

输入

输入按以下格式从标准输入读入：

• $N$ $M$
• $S$
• $A_1$ $B_1$
• $\vdots$
• $A_M$ $B_M$

输出

输出答案。

数据范围

• $N$、$M$ 为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。
• $A_i$、$B_i$ 为整数。
• $1 \leq A_i < B_i \leq N$
• $(A_1, B_1), \dots, (A_M, B_M)$ 两两不同。

5 3
miria
1 3
2 5
4 5

6

操作结束后 $S$ 可能变成以下六个字符串：

• marii
• mirai
• miria
• ramii
• rimai
• rimia

6 6
yiwayi
1 2
1 3
2 3
4 5
4 6
5 6

18

29 25
hexakosioihexekontahexaphobia
1 2
1 4
1 6
1 8
1 15
1 16
2 3
3 4
4 20
5 6
5 8
8 22
8 23
9 15
9 17
11 21
12 20
13 19
14 29
15 28
16 17
18 19
18 21
19 20
20 21

346192062

• 来源：AtCoder ABC 470 F

子任务设置

• 子任务 1（150 分）：$N,M \le 2000$。
• 子任务 2（150 分）：$N,M \le 5 \times 10^4$。
• 子任务 3（200 分）：无特殊限制。