← 返回题目列表

Codeforces · 1906/H

H. 双胞胎朋友

中文机器翻译题面 查看原题

您遇到了两个新朋友,他们是双胞胎。双胞胎中较大的一个的名字是 $$$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$$$ 求模答案。

输入

第一行由两个整数 $$$N$$$ $$$M$$$ ($$$1 \leq N \leq M \leq 200\,000$$$) 组成。

第二行由长度为 $$$N$$$ 的字符串 $$$A$$$ 组成。

第三行由长度为 $$$M$$$ 的字符串 $$$B$$$ 组成。

所有字符串仅包含大写字母。

输出

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

示例

输入 #1

3 4
AMA
ANAB

输出 #1

9

输入 #2

5 8
BINUS
BINANUSA

输出 #2

120

输入 #3

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA

输出 #3

151362308

输入#4

4 4
UDIN
ASEP

输出#4

0

注意

示例输入/输出 #1 的说明

$$$9$$$ 对是:

- (AAM,AAN),
- (AAM,ABN),
- (AAM,禁令),
- (AMA,全日空),
- (AMA, ANB),
- (AMA,BNA),
- (MAA,NAA),
- (MAA、NAB),以及
- (MAA、NBA)。

示例输入/输出#2 的说明

$$$120$$$ 对是其中 $$$A'$$$ 是 BINUS 排列且 $$$B' = A'$$$ 的对。