Twin Friends

Time limit2sMemory limit1024 MB

Summary

Count pairs of a permutation A' of A and a length-N string B' from B, where each B' letter equals or follows the matching A' letter, modulo 998244353.

Level: Medium6 of 10
Topics: Combinatorics, Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

You meet two new friends who are twins. The elder twin's name is $A$ , which has $N$ characters. The younger twin's name is $B$ , which has $M$ characters. $N \le M$ .

You want to give each of them a nickname. For the elder twin, you choose any permutation of $A$ as the nickname $A'$ . For the younger twin, you remove exactly $M - N$ characters from some permutation of $B$ to form the nickname $B'$ .

The nicknames must satisfy this condition: for each $i$ with $1 \le i \le N$ , $B'_i$ is either $A'_i$ or the letter that follows $A'_i$ in the alphabet (if that letter exists).

Count the number of different pairs $(A', B')$ that satisfy the condition. Two pairs are different if at least one of their nicknames differs. Print the count modulo $998244353$ .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le M \le 200000$ ).

The second line contains the string $A$ of length $N$ .

The third line contains the string $B$ of length $M$ .

All strings consist only of uppercase letters.

Output

Print one integer, the number of valid pairs $(A', B')$ modulo $998244353$ .

Examples4

Example 1
Input
```
3 4
AMA
ANAB
```
Expected output
```
9
```
Example 2
Input
```
5 8
BINUS
BINANUSA
```
Expected output
```
120
```

Example 3

Input

15 30
BINUSUNIVERSITY
BINANUSANTARAUNIVERSITYJAKARTA

Expected output

151362308

Example 4
Input
```
4 4
UDIN
ASEP
```
Expected output
```
0
```