题目描述

定义一个 01 串是平衡的当且仅当它的 0 和 1 的个数相同。

现在给定 $n,k$ 和一个长度为 $m$ 的 01 串 $S$，求有多少长度为 $n$ 且以 $S$ 为前缀的 01 串满足其不存在长度为 $k$ 的平衡子串，对 $998244353$ 取模。

输入格式

第一行，两个整数 $n$，$k$ 和 $m$ 表示串的长度，平衡串的限制和 $S$ 的长度。

接下来一行一个长度为 $m$ 的 01 串表示 $S$。

输出格式

一行一个整数，表示答案模 $998244353$ 后的结果。

样例 1

输入

5 4 2
01

输出

3

样例 2

输入

13 6 0

输出

996

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le m+1 \le k \le n \le 114$ 且 $k$ 是偶数。