F - Googol Swaps 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。
以下の操作を ちょうど 10^{100} 回実行したあとの S としてあり得るものの個数を 998244353 で割ったあまりを求めてください。

  • 1 以上 M 以下の整数 i をひとつ選び、S の A_i 文字目と B_i 文字目を入れ替える。

制約

  • 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) は相異なる

入力

入力は以下の形式で標準入力から与えられる。

N M
S
A_1 B_1
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

5 3
miria
1 3
2 5
4 5

出力例 1

6

最終的な S として、以下の 6 通りがあり得ます。

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

入力例 2

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

出力例 2

18

入力例 3

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

出力例 3

346192062

Score : 500 points

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.

Sample Input 1

5 3
miria
1 3
2 5
4 5

Sample Output 1

6

The following six strings are possible as the final S:

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

Sample Input 2

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

Sample Output 2

18

Sample Input 3

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

Sample Output 3

346192062