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