#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
bool notPrime[N];
vector<int> primes;
void calc_prime() {
  notPrime[1] = true;
  notPrime[2] = false;
  for (int i = 2; i * i < N; ++i) {
    if (!notPrime[i]) {
      primes.push_back(i);
      int j = i * i;
      while (j < N) {
        notPrime[j] = true;
        j += i;
      }
    }
  }
}
long long mod = 998244353;
long long cnk[5001][5001];
void prep(int k) {
  cnk[0][0] = 1;
  for (int j = 1; j <= k; ++j) {
    cnk[j][0] = 1;
    for (int i = 1; i <= j; ++i) {
      cnk[j][i] = (cnk[j - 1][i - 1] + cnk[j - 1][i]) % mod;
    }
  }
}
int main() {
  int n, k;
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  prep(n);
  string s;
  cin >> s;
  long long ans = 0;
  vector<long long> p(n);
  long long pref = 0;
  for (int i = 0; i < n; ++i) {
    p[i] = pref;
    if (s[i] == '1') {
      ++p[i];
    }
    pref = p[i];
  }
  int l = -1, r = -1;
  for (int(i) = 0; (i) < (n); ++(i)) {
    if (p[i] == k) {
      r = i;
      l = 0;
    }
  }
  if (l == -1) {
    cout << 1 << endl;
    return 0;
  }
  ans += cnk[r - l + 1][k];
  int pr = r, pl = l;
  vector<long long> a;
  a.push_back(ans);
  while (r < n - 1) {
    ++r;
    while (r < n - 1 && s[r + 1] == '0') {
      ++r;
    }
    while (s[l] != '1') {
      ++l;
    }
    ++l;
    if (l > pr) {
      ans = (ans + cnk[r - l + 1][k]) % mod;
      ans = (ans + mod - 1) % mod;
      a.push_back(ans);
      pr = r;
      pl = l;
      continue;
    }
    long long cur = cnk[pr - l + 1][k - 1];
    long long nw = cnk[r - l + 1][k];
    ans += (nw - cur + mod) % mod;
    ans %= mod;
    pr = r;
    pl = l;
  }
  cout << ans << endl;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

You are given a binary string (i. e. a string consisting of characters 0 and/or 1) s of length n. You can perform the following operation with the string s at most once: choose a substring (a contiguous subsequence) of s having exactly k characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).

Calculate the number of different strings which can be obtained from s by performing this operation at most once.

Input

The first line contains two integers n and k (2 ≤ n ≤ 5000; 0 ≤ k ≤ n).

The second line contains the string s of length n, consisting of characters 0 and/or 1.

Output

Print one integer — the number of different strings which can be obtained from s by performing the described operation at most once. Since the answer can be large, output it modulo 998244353.

Examples

Input


7 2
1100110


Output


16


Input


5 0
10010


Output


1


Input


8 1
10001000


Output


10


Input


10 8
0010011000


Output


1

Note

Some strings you can obtain in the first example:

  * to obtain 0110110, you can take the substring from the 1-st character to the 4-th character, which is 1100, and reorder its characters to get 0110; 
  * to obtain 1111000, you can take the substring from the 3-rd character to the 7-th character, which is 00110, and reorder its characters to get 11000; 
  * to obtain 1100101, you can take the substring from the 5-th character to the 7-th character, which is 110, and reorder its characters to get 101. 



In the second example, k = 0 so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
bool notPrime[N];
vector<int> primes;
void calc_prime() {
  notPrime[1] = true;
  notPrime[2] = false;
  for (int i = 2; i * i < N; ++i) {
    if (!notPrime[i]) {
      primes.push_back(i);
      int j = i * i;
      while (j < N) {
        notPrime[j] = true;
        j += i;
      }
    }
  }
}
long long mod = 998244353;
long long cnk[5001][5001];
void prep(int k) {
  cnk[0][0] = 1;
  for (int j = 1; j <= k; ++j) {
    cnk[j][0] = 1;
    for (int i = 1; i <= j; ++i) {
      cnk[j][i] = (cnk[j - 1][i - 1] + cnk[j - 1][i]) % mod;
    }
  }
}
int main() {
  int n, k;
  cin >> n >> k;
  if (k == 0) {
    cout << 1 << endl;
    return 0;
  }
  prep(n);
  string s;
  cin >> s;
  long long ans = 0;
  vector<long long> p(n);
  long long pref = 0;
  for (int i = 0; i < n; ++i) {
    p[i] = pref;
    if (s[i] == '1') {
      ++p[i];
    }
    pref = p[i];
  }
  int l = -1, r = -1;
  for (int(i) = 0; (i) < (n); ++(i)) {
    if (p[i] == k) {
      r = i;
      l = 0;
    }
  }
  if (l == -1) {
    cout << 1 << endl;
    return 0;
  }
  ans += cnk[r - l + 1][k];
  int pr = r, pl = l;
  vector<long long> a;
  a.push_back(ans);
  while (r < n - 1) {
    ++r;
    while (r < n - 1 && s[r + 1] == '0') {
      ++r;
    }
    while (s[l] != '1') {
      ++l;
    }
    ++l;
    if (l > pr) {
      ans = (ans + cnk[r - l + 1][k]) % mod;
      ans = (ans + mod - 1) % mod;
      a.push_back(ans);
      pr = r;
      pl = l;
      continue;
    }
    long long cur = cnk[pr - l + 1][k - 1];
    long long nw = cnk[r - l + 1][k];
    ans += (nw - cur + mod) % mod;
    ans %= mod;
    pr = r;
    pl = l;
  }
  cout << ans << endl;
}

```