#include #include #include #include using namespace std; #include using mint = atcoder::modint998244353; vector> ncr; vector pow2; mint solve(int N, int K, string X) { vector dp(N + 1); dp[N] = 1; // dp[# of candidate elements] for (auto c : X) { vector dpnxt(dp.size()); const bool x = (c == '1'); for (int i = K; i <= N; ++i) { for (int j = 0; j <= i; ++j) { if (x) { // j : # of 1 if (i - j < K) dpnxt[i] += dp[i] * pow2[N - i] * ncr[i][j]; } if (!x) { // j : # of 0 if (j >= K) dpnxt[j] += dp[i] * pow2[N - i] * ncr[i][j]; } } } dp = dpnxt; } return accumulate(dp.begin(), dp.end(), mint(0)); } int main() { int N, M, K; string X; cin >> N >> M >> K >> X; ncr.assign(201, vector(201)); for (int i = 0; i < int(ncr.size()); ++i) ncr[i][0] = 1; for (int i = 1; i < int(ncr.size()); ++i) { for (int j = 1; j < int(ncr[i].size()); ++j) ncr[i][j] = ncr[i - 1][j - 1] + ncr[i - 1][j]; } pow2.assign(201, 1); for (int i = 1; i < int(pow2.size()); ++i) pow2[i] = pow2[i - 1] * 2; cout << solve(N, K, X).val() << '\n'; }