题目背景

本题由

原题链接（注意原题与加强版有且仅有理解方式中的式子不同、模数不同、数据范围不同）。

题目描述

注：为了方便描述，下文所有字符串起始位置都为 $1$，即都从 $1$ 开始标号。

小 L 将每次生草前的原文和生草后的结果看作两个仅由小写字母组成的两个字符串 $A$ 和 $B$。

我们按如下方式定义「分割数列」和「分割串」：

• 对于一个长度为 $n$ 的字符串，定义它的一条「分割数列」为：存在长度为 $k+2$ 的数列 $p$，使得 $0=p_0<p_1<p_2<...<p_k<p_{k+1}=n+1$。对于一条「分割数列」，定义其「分割串」为 $p_i+1$ 到 $p_{i+1}-1$ 之间字符构成的子串（$i \in[0,k]$）（可以为空串）。显然，对于一条长度为 $k+2$ 的分割数列，一共有 $k+1$ 个分割串。

• 对于同一个字符串，两条分割数列（$p$ 和 $q$）不同当且仅当两条数列长度不同（$k_1\neq k_2$），或存在 $i$ 使得 $p_i\neq q_i$。

不同人对于同样的原文和结果，他们的理解方式都是不同的。我们按如下方式定义一种理解方式：

• 对于字符串 $A$ 和 $B$，我们为这两个字符串各找一条分割数列（$p$ 和 $q$），这两个分割数列满足以下要求：

1. 两个分割数列长度相等（$k_1=k_2$）。
2. 对于任意 $i$，有 $A[p_i]=B[q_i]$，即 $A$ 第 $p_i$ 个位置的字符与 $B$ 第 $q_i$ 个位置的字符相同。

• 定义这种理解方式的「生草程度」为此时两个字符串的所有分割串长度的 $t$ 次方和，即 $\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$。

• 两种理解方式不同当且仅当两种理解方式的 $p$ 不同，或两种理解方式的 $q$ 不同。

小 L 想要知道所有理解方式的生草程度之和的结果。由于他（也）不喜欢 $998244353$ 这个数，他不希望你告诉他的结果会是这个数，所以你要将结果对 $998244353$ 取模。

输入格式

第一行有三个正整数 $n,m,t$。

接下来一行有一个长度为 $n$ 的字符串，表示字符串 $A$。

接下来一行有一个长度为 $m$ 的字符串，表示字符串 $B$。

输出格式

一行，一个整数，表示答案对 $998244353$ 取模的结果。

3 4 2
abc
bacb

74

7 8 5
ccbbacb
bbbdadba

337322

3 4 1000000
abc
bacb

424285944

提示

对于样例一，一共有以下理解方式：

• $p=\{0,4\},q=\{0,5\}$，生草程度为 $25$。
• $p=\{0,1,4\},q=\{0,2,5\}$，生草程度为 $9$。
• $p=\{0,2,4\},q=\{0,1,5\}$，生草程度为 $11$。
• $p=\{0,2,4\},q=\{0,4,5\}$，生草程度为 $11$。
• $p=\{0,3,4\},q=\{0,3,5\}$，生草程度为 $9$。
• $p=\{0,1,2,4\},q=\{0,2,4,5\}$，生草程度为 $3$。
• $p=\{0,1,3,4\},q=\{0,2,3,5\}$，生草程度为 $3$。
• $p=\{0,2,3,4\},q=\{0,1,3,5\}$，生草程度为 $3$。

总生草程度为 $74$。

数据范围

「本题采用捆绑测试」

• 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\%$ )：无特殊限制。

对于 $100\%$ 的数据，$n,m\leq 1000,t\leq 1000000$，$A$ 和 $B$ 仅包含小写字母。