说明

你遇到了两位新朋友，他们是一对双胞胎。哥哥的名字是 $A$，由 $N$ 个字符组成。弟弟的名字是 $B$，由 $M$ 个字符组成。已知 $N \leq M$。

你想给他们每人取一个昵称。对于哥哥，你可以任选 $A$ 的一个排列作为昵称。对于弟弟，你可以从 $B$ 的任意一个排列中恰好删除 $M-N$ 个字符，得到昵称。分别记哥哥和弟弟的昵称为 $A'$ 和 $B'$。

你希望昵称满足以下要求：对于每一个 $1 \leq i \leq N$，$B'_i$ 必须等于 $A'_i$ 或者字母表中紧跟在 $A'_i$ 之后的那个字母（如果存在的话）。

请你计算满足要求的不同昵称对 $(A', B')$ 的数量。如果至少有一个昵称不同，则认为两个昵称对不同。由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq M \leq 200\,000$）。

第二行包含一个长度为 $N$ 的字符串 $A$。

第三行包含一个长度为 $M$ 的字符串 $B$。

所有字符串均由大写英文字母组成。

输出格式

输出一个整数，表示满足条件的不同昵称对 $(A', B')$ 的数量，对 $998\,244\,353$ 取模。

3 4
AMA
ANAB

9

5 8
BINUS
BINANUSA

120

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA

151362308

4 4
UDIN
ASEP

0

提示

样例输入输出 1 说明

这 $9$ 对昵称分别为：

• (AAM, AAN),
• (AAM, ABN),
• (AAM, BAN),
• (AMA, ANA),
• (AMA, ANB),
• (AMA, BNA),
• (MAA, NAA),
• (MAA, NAB),
• (MAA, NBA)。

样例输入输出 2 说明

这 $120$ 对昵称是所有 $A'$ 是 BINUS 的排列且 $B' = A'$ 的情况。

由 ChatGPT 4.1 翻译