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