A binary string is defined as balanced if and only if it contains an equal number of 0s and 1s.
Given $n$, $k$, and a binary string $S$ of length $m$, find the number of binary strings of length $n$ that have $S$ as a prefix and do not contain any balanced substring of length $k$. Output the answer modulo $998244353$.
Input
The first line contains three integers $n$, $k$, and $m$, representing the total length of the string, the constraint on the balanced substring, and the length of $S$, respectively.
The next line contains a binary string $S$ of length $m$.
Output
Output a single integer representing the answer modulo $998244353$.
Examples
Input 1
5 4 2 01
Output 1
3
Input 2
13 6 0
Output 2
996
Constraints
For $100\%$ of the data, it is guaranteed that $1\le m+1\le k\le n\le 114$ and $k$ is even.
| Subtask ID | $n\le$ | Special Properties | Score | Dependencies |
|---|---|---|---|---|
| $1$ | $20$ | $10$ | ||
| $2$ | $114$ | $k\le 20$ | $10$ | $1$ |
| $3$ | $66$ | $30$ | $1$ | |
| $4$ | $114$ | $m=0$ | $20$ | |
| $5$ | $114$ | $30$ | $2,3,4$ |