Lisa 编写了一个程序来解决最长公共子串问题。她随后使用该程序，针对两个由字符 '0' 和 '1' 组成的字符串 $s$ 和 $t$，找到了一个既是 $s$ 的子串又是 $t$ 的子串的最长字符串 $w$。如果存在多个这样的最长字符串，她会找到其中任意一个。

值得注意的是，Lisa 找到的 $w$ 的长度非常小——最多为 3。

Lisa 记得 $n$（$s$ 的长度）、$m$（$t$ 的长度）以及 $w$，但她不记得字符串 $s$ 和 $t$ 本身了。现在她想知道，有多少对字符串 $(s, t)$ 满足它们的长度分别为 $n$ 和 $m$，由字符 '0' 和 '1' 组成，且 $w$ 是它们的最长公共子串之一。

请帮助 Lisa 计算这些字符串对的数量，结果对 $998\,244\,353$ 取模。注意，如果 $n = m$ 且 $s \neq 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$，由字符 '0' 和 '1' 组成。

输出格式

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

样例

样例输入 1

2 2 1
1

样例输出 1

6

样例输入 2

3 4 2
01

样例输出 2

28

样例输入 3

7 5 3
110

样例输出 3

399

样例输入 4

23 42 3
000

样例输出 4

174497840

说明

注意，如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除零个或多个字符，并从结尾删除零个或多个字符得到，则称 $a$ 是 $b$ 的子串。

在第一个测试样例中，所有满足条件的字符串对为 (“01”, “10”), (“01”, “11”), (“10”, “01”), (“10”, “11”), (“11”, “01”) 和 (“11”, “10”)。