该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.
Find the number, modulo $998244353$, of strings that $S$ can become after performing the following operation exactly $10^{100}$ times.

• Choose an integer $i$ between $1$ and $M$, inclusive, and swap the $A_i$-th and $B_i$-th characters of $S$.

Constraints

• $N$ and $M$ are integers.
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $A_i$ and $B_i$ are integers.
• $1 \leq A_i < B_i \leq N$
• $(A_1, B_1), \dots, (A_M, B_M)$ are pairwise distinct.

Input

The input is given from Standard Input in the following format:

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

Output

Output the answer.

5 3
miria
1 3
2 5
4 5

6

The following six strings are possible as the final $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

• Source: AtCoder ABC 470 F