310899: CF1906H. Twin Friends

H. Twin Friendstime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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$.

Input

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.

Output

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

ExamplesInput

3 4
AMA
ANAB

Output

9

Input

5 8
BINUS
BINANUSA

Output

120

Input

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA

Output

151362308

Input

4 4
UDIN
ASEP

Output

0

Note

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'$.

题目大意：
你遇到了一对双胞胎新朋友，分别给他们的昵称起名。大双胞胎的名字是A，由N个字符组成；小双胞胎的名字是B，由M个字符组成，已知N≤M。你想要为大双胞胎选择A的任意排列作为昵称，而为小双胞胎，你想要从B的任意排列中删除恰好M-N个字符。设大双胞胎和小双胞胎的昵称为A'和B'。你希望昵称满足以下要求：对于每个i（1≤i≤N），B'_i必须等于A'_i或者紧跟在A'_i之后的字母（如果存在这样的下一个字母）。确定满足要求的不同的昵称对(A', B')的数量。如果结果很大，请找到模998244353的结果。

输入输出数据格式：
输入：
- 第一行包含两个整数N M（1≤N≤M≤200000）。
- 第二行包含一个长度为N的字符串A。
- 第三行包含一个长度为M的字符串B。
- 所有字符串仅由大写字母组成。

输出：
- 输出一个整数，表示满足要求的不同的昵称对(A', B')的数量，模998244353。

示例：
输入：
3 4
AMA
ANAB
输出：
9

输入：
5 8
BINUS
BINANUSA
输出：
120

输入：
15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA
输出：
151362308

输入：
4 4
UDIN
ASEP
输出：
0题目大意： 你遇到了一对双胞胎新朋友，分别给他们的昵称起名。大双胞胎的名字是A，由N个字符组成；小双胞胎的名字是B，由M个字符组成，已知N≤M。你想要为大双胞胎选择A的任意排列作为昵称，而为小双胞胎，你想要从B的任意排列中删除恰好M-N个字符。设大双胞胎和小双胞胎的昵称为A'和B'。你希望昵称满足以下要求：对于每个i（1≤i≤N），B'_i必须等于A'_i或者紧跟在A'_i之后的字母（如果存在这样的下一个字母）。确定满足要求的不同的昵称对(A', B')的数量。如果结果很大，请找到模998244353的结果。 输入输出数据格式： 输入： - 第一行包含两个整数N M（1≤N≤M≤200000）。 - 第二行包含一个长度为N的字符串A。 - 第三行包含一个长度为M的字符串B。 - 所有字符串仅由大写字母组成。 输出： - 输出一个整数，表示满足要求的不同的昵称对(A', B')的数量，模998244353。 示例： 输入： 3 4 AMA ANAB 输出： 9 输入： 5 8 BINUS BINANUSA 输出： 120 输入： 15 30 BINUSUNIVERSITY BINANUSANTARAUNIVERSITYJAKARTA 输出： 151362308 输入： 4 4 UDIN ASEP 输出： 0