题目描述

Lisa 编写了一个程序来解决最长公共子串问题。

对于某两个仅由字符 0 和 1 组成的字符串 $s,t$，她使用程序找到了一个同时为 $s$ 和 $t$ 子串的最长字符串 $w$。若最长公共子串不唯一，她任意选择了其中一个。

特别地，她得到的 $w$ 很短，长度至多为 $3$。

Lisa 还记得 $s$ 的长度 $n$、$t$ 的长度 $m$ 以及字符串 $w$，但已经忘记了 $s$ 和 $t$ 本身。

请计算有多少个有序字符串对 $(s,t)$ 满足：

• $|s|=n$，$|t|=m$；
• $s,t$ 均只由 0 和 1 组成；
• $w$ 是 $s$ 和 $t$ 的某个最长公共子串。

答案对 $998\,244\,353$ 取模。

注意，当 $n=m$ 且 $s\ne t$ 时，$(s,t)$ 和 $(t,s)$ 被视为不同的字符串对。

输入格式

第一行包含三个整数 $n,m,k$，分别表示字符串 $s,t,w$ 的长度。

第二行包含一个长度为 $k$、仅由 0 和 1 组成的字符串 $w$。

数据范围

$$1\le n,m\le 100,$$ $$1\le k\le \min(3,n,m).$$

输出格式

输出一个整数，表示满足条件的有序字符串对 $(s,t)$ 的数量，对 $998\,244\,353$ 取模。

样例 1

2 2 1
1

6

样例 2

3 4 2
01

28

样例 3

7 5 3
110

399

样例 4

23 42 3
000

174497840

样例说明

在样例 1 中，所有满足条件的字符串对为：

$$(\texttt{01},\texttt{10}), (\texttt{01},\texttt{11}), (\texttt{10},\texttt{01}), (\texttt{10},\texttt{11}), (\texttt{11},\texttt{01}), (\texttt{11},\texttt{10}).$$

字符串 $a$ 是字符串 $b$ 的子串，当且仅当可以从 $b$ 的开头删除若干字符，再从结尾删除若干字符，得到 $a$；删除的字符数均可为 $0$。