P12116 [NWRRC2024] Longest Common Substring

Lisa 编写了一个解决最长公共子串问题的程序。她使用该程序对两个由字符 $\tt{0}$ 和 $\tt{1}$ 组成的字符串 $s$ 和 $t$ 进行计算，找到了它们的最长公共子串 $w$。当存在多个相同长度的最长公共子串时，她任意选择其中一个。 值得注意的是，Lisa 找到的 $w$ 长度非常小——最多为 3。 Lisa 记得 $n$（$s$ 的长度）、$m$（$t$ 的长度）和 $w$，但她不记得字符串 $s$ 和 $t$ 本身。现在她想知道有多少对字符串 $(s, t)$ 满足：它们的长度分别为 $n$ 和 $m$，由字符 $\tt{0}$ 和 $\tt{1}$ 组成，并且 $w$ 是它们的最长公共子串之一。 请帮助 Lisa 计算这个对数，结果对 $998\,244\,353$ 取模。注意当 $n = m$ 且 $s \ne t$ 时，$(s, t)$ 和 $(t, s)$ 被视为不同的对。

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示字符串 $s$、$t$ 和 $w$ 的长度（$1 \le n, m \le 100$；$1 \le k \le \min(3, n, m)$）。 第二行包含一个长度为 $k$ 的字符串 $w$，由字符 $\tt{0}$ 和 $\tt{1}$ 组成。

输出满足条件的字符串对 $(s, t)$ 的数量，结果对 $998\,244\,353$ 取模。

注意，字符串 $a$ 是字符串 $b$ 的子串，当且仅当 $a$ 可以通过从 $b$ 的开头和结尾删除零个或多个字符得到。 在第一个测试用例中，所有满足条件的字符串对为 ($\tt{01}$, $\tt{10}$)、($\tt{01}$, $\tt{11}$)、($\tt{10}$, $\tt{01}$)、($\tt{10}$, $\tt{11}$)、($\tt{11}$, $\tt{01}$) 和 ($\tt{11}$, $\tt{10}$)。