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

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 a single integer representing number of different pairs $ (A', B') $ that satisfy the requirement, modulo $ 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' $ .