P6695 谷歌翻(sheng)译(cao)机（加强版）

本题由@[wolfind](https://www.luogu.com.cn/user/104593)提供。 [原题链接](https://www.luogu.com.cn/problem/P6693)（注意原题与加强版**有且仅有**`理解方式`中的**式子不同**、**模数不同**、**数据范围不同**）。

**注：为了方便描述，下文所有字符串起始位置都为 $1$，即都从 $1$ 开始标号。** 小 L 将每次生草前的原文和生草后的结果看作两个**仅由小写字母组成**的两个字符串 $A$ 和 $B$。 我们按如下方式定义「分割数列」和「分割串」： - 对于一个长度为 $n$ 的字符串，定义它的一条「分割数列」为：存在长度为 $k+2$ 的数列 $p$，使得 $0=p_0

第一行有三个正整数 $n,m,t$。 接下来一行有一个长度为 $n$ 的字符串，表示字符串 $A$。 接下来一行有一个长度为 $m$ 的字符串，表示字符串 $B$。

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

对于样例一，一共有以下理解方式： + $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$ **仅包含小写字母**。