Background

This problem is provided by

Original link (note that the original problem and the enhanced version differ only in the formula in interpretation method, the modulus, and the Constraints).

Problem Description

Note: For convenience, in the following, all strings are 1-indexed, i.e. positions start from $1$.

Xiao L treats the original text before each meme-making and the result after meme-making as two strings $A$ and $B$, both consisting only of lowercase letters.

We define a “split sequence” and “split substring” as follows:

• For a string of length $n$, a “split sequence” is defined as: there exists a sequence $p$ of length $k+2$ such that $0=p_0<p_1<p_2<...<p_k<p_{k+1}=n+1$. For a split sequence, its “split substrings” are the substrings formed by the characters from position $p_i+1$ to $p_{i+1}-1$ ($i \in[0,k]$) (they can be empty strings). Clearly, for a split sequence of length $k+2$, there are $k+1$ split substrings in total.

• For the same string, two split sequences ($p$ and $q$) are different if and only if the lengths of the two sequences are different ($k_1\neq k_2$), or there exists an $i$ such that $p_i\neq q_i$.

Different people may have different interpretation methods for the same original text and result. We define an interpretation method as follows:

• For strings $A$ and $B$, we find one split sequence for each of them ($p$ and $q$). These two split sequences must satisfy:

1. The two split sequences have the same length ($k_1=k_2$).
2. For any $i$, $A[p_i]=B[q_i]$, i.e. the character at position $p_i$ in $A$ is the same as the character at position $q_i$ in $B$.

• Define the “meme level” (shengcao degree) of this interpretation method as the sum of the $t$-th powers of the lengths of all split substrings in the two strings, i.e. $\sum\limits_{i=0}^{k_1}(p_{i+1}-p_i-1)^t+\sum\limits_{i=0}^{k_2}(q_{i+1}-q_i-1)^t$.

• Two interpretation methods are different if and only if their $p$ are different, or their $q$ are different.

Xiao L wants to know the sum of the meme levels over all interpretation methods. Since he (also) does not like the number $998244353$, he does not want you to tell him the result as that number, so you need to take the result modulo $998244353$.

Input Format

The first line contains three positive integers $n,m,t$.

The next line contains a string of length $n$, representing string $A$.

The next line contains a string of length $m$, representing string $B$.

Output Format

One line containing one integer, the answer modulo $998244353$.

3 4 2
abc
bacb

74

7 8 5
ccbbacb
bbbdadba

337322

3 4 1000000
abc
bacb

424285944

Hint

For Sample 1, there are the following interpretation methods:

• $p=\{0,4\},q=\{0,5\}$, meme level is $25$.
• $p=\{0,1,4\},q=\{0,2,5\}$, meme level is $9$.
• $p=\{0,2,4\},q=\{0,1,5\}$, meme level is $11$.
• $p=\{0,2,4\},q=\{0,4,5\}$, meme level is $11$.
• $p=\{0,3,4\},q=\{0,3,5\}$, meme level is $9$.
• $p=\{0,1,2,4\},q=\{0,2,4,5\}$, meme level is $3$.
• $p=\{0,1,3,4\},q=\{0,2,3,5\}$, meme level is $3$.
• $p=\{0,2,3,4\},q=\{0,1,3,5\}$, meme level is $3$.

The total meme level is $74$.

Constraints

“This problem uses bundled subtasks.”

• Subtask 1 ( $20\%$ ): $n,m\leq 50,t\leq 2$.
• Subtask 2 ( $30\%$ ): $n,m\leq 200,t\leq 2$.
• Subtask 3 ( $20\%$ ): $t\leq 10$.
• Subtask 4 ( $30\%$ ): no special restrictions.

For $100\%$ of the testdata, $n,m\leq 1000,t\leq 1000000$, and $A$ and $B$ contain only lowercase letters.

Translated by ChatGPT 5