CF1906H.Twin Friends

You meet two new friends who are twins. The name of the elder twin is $A$, which consists of $N$ characters. While the name of the younger twin is $B$, which consists of $M$ characters. It is known that $N \leq M$.

You want to call each of them with a nickname. For the elder twin, you want to pick any permutation of $A$ as the nickname. For the younger twin, you want to remove exactly $M - N$ characters from any permutation of $B$. Denote the nicknames of the elder twin and the younger twin as $A'$ and $B'$, respectively.

You want the nicknames to satisfy the following requirement. For each $i$ that satisfies $1 \leq i \leq N$, $B'_i$ must be equal to either $A'_i$ or the next letter that follows alphabetically after $A'_i$ (if such a next letter exists).

Determine the number of different pairs of nicknames $(A', B')$ that satisfy the requirement. Two pairs of nicknames are considered different if at least one of the nicknames are different. As the result might be large, find the answer modulo $998\,244\,353$.

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

你想分别为她们取一个昵称。对于姐姐，你想从 $A$ 的任意一个排列中选取作为昵称；对于妹妹，你想从 $B$ 的任意一个排列中恰好删去 $M - N$ 个字符，从而得到她的昵称。分别记姐姐和妹妹的昵称为 $A'$ 和 $B'$。

你希望这些昵称满足如下要求：对每个满足 $1 \leq i \leq N$ 的下标 $i$，$B'_i$ 必须等于 $A'_i$，或等于紧接在 $A'_i$ 之后的、按字母表顺序的下一个字母（如果该下一个字母存在）。

请计算满足上述要求的不同昵称对 $(A', B')$ 的数量。若两个昵称对中至少有一个昵称不同，则认为它们是不同的。由于答案可能很大，请将结果对 $998\,244\,353$ 取模。

The first line consists of two integers $N$ $M$ ($1 \leq N \leq M \leq 200\,000$).

The second line consists of a string $A$ of length $N$.

The third line consists of a string $B$ of length $M$.

All strings consist of only upper-case letters.

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

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

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

所有字符串仅由大写字母组成。

Output a single integer representing number of different pairs $(A', B')$ that satisfy the requirement, modulo $998\,244\,353$.

输出一个整数，表示满足要求的不同数对 $(A', B')$ 的数量，结果对 $998\,244\,353$ 取模。

Explanation for the sample input/output #1

The $9$ pairs are:

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

Explanation for the sample input/output #2

The $120$ pairs are the pairs where $A'$ is a permutation of BINUS and $B' = A'$.

样例输入/输出 #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'$ 的字符串对。