AT_abc470_f [ABC470F] Googol Swaps
题目描述
给定一个由小写英文字母组成的长度为 $N$ 的字符串 $S$。
请计算将下述操作**恰好**执行 $10^{100}$ 次后，$S$ 能变成的不同字符串的个数，并对 $998244353$ 取模。
- 可以选择一个 $i$，满足 $1 \leq i \leq M$，并交换 $S$ 的第 $A_i$ 个字符和第 $B_i$ 个字符的位置。
输入格式
输入通过标准输入给出，格式如下：
> $N$ $M$
> $S$
> $A_1$ $B_1$
> $\vdots$
> $A_M$ $B_M$
输出格式
输出答案。
说明/提示
### 样例解释 1
经过操作后，最终可能的 $S$ 有以下六种：
- `marii`
- `mirai`
- `miria`
- `ramii`
- `rimai`
- `rimia`
### 约束条件
- $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)$ 两两不同。
由 ChatGPT 5 翻译