Longest Common Substring
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lisa wrote a program to solve the Longest Common Substring problem. She then used the program to find, for some two strings $$$s$$$ and $$$t$$$ consisting of characters '0' and '1', the longest string $$$w$$$ that is a substring of both $$$s$$$ and $$$t$$$. If there were multiple such longest strings, she found an arbitrary one.

Notably, the length of $$$w$$$ Lisa found was very small — at most 3.

Lisa remembers $$$n$$$ (the length of $$$s$$$), $$$m$$$ (the length of $$$t$$$), and $$$w$$$, but she doesn't remember strings $$$s$$$ and $$$t$$$ themselves. Now she wonders how many pairs of strings $$$s$$$ and $$$t$$$ exist such that they have lengths $$$n$$$ and $$$m$$$, respectively, consist of characters '0' and '1', and have $$$w$$$ as one of their longest common substrings.

Help Lisa and find this number of pairs modulo $$$998\,244\,353$$$. Note that if $$$n = m$$$ and $$$s \ne t$$$, pairs $$$(s, t)$$$ and $$$(t, s)$$$ are considered distinct.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$, denoting the lengths of the strings $$$s$$$, $$$t$$$, and $$$w$$$ ($$$1 \le n, m \le 100$$$; $$$1 \le k \le \min(3, n, m)$$$).

The second line contains the string $$$w$$$ of length $$$k$$$ consisting of characters '0' and '1'.

Output

Print the number of pairs of strings $$$(s, t)$$$ that have $$$w$$$ as one of their longest common substrings, modulo $$$998\,244\,353$$$.

Examples

Input
2 2 1
1
Output
6
Input
3 4 2
01
Output
28
Input
7 5 3
110
Output
399
Input
23 42 3
000
Output
174497840

Note

Note that a string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting zero or more characters from the beginning and zero or more characters from the end.

In the first test, all pairs of strings satisfying the conditions are ("01", "10"), ("01", "11"), ("10", "01"), ("10", "11"), ("11", "01"), and ("11", "10").