#include <bits/stdc++.h>
using namespace std;
long long int calculate(long long int p, long long int q) {
  long long int modx = 998244353, expo;
  expo = modx - 2;
  while (expo) {
    {
      if (expo & 1) p = (p * q) % modx;
    }
    q = (q * q) % modx;
    expo >>= 1;
  }
  return p % modx;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % p;
    }
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  t = 1;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    string s;
    long long int ans = 1;
    cin >> s;
    if (k == 0) {
      cout << 1 << "\n";
      continue;
    }
    long long int i = 0, j = 0;
    long long int dp[n + 5][k + 5];
    memset(dp, 0, sizeof(dp));
    for (int p = 1; p <= k; p++) {
      dp[0][p] = dp[0][p - 1] + 1;
    }
    for (int p = 1; p <= n; p++) {
      for (int q = 1; q <= k; q++)
        dp[p][q] = (dp[p - 1][q] + dp[p][q - 1]) % 998244353;
    }
    long long int zero = 0, lastzero = 0, one = 0, b = 0;
    while (i < n) {
      if (s[i] == '0') {
        zero++;
        if (one == k) lastzero++;
      } else
        one++;
      if (one > k) {
        for (int p = 0; p < zero; p++) {
          ans = (ans + dp[p][k]) % 998244353;
        }
        long long int temp = 0;
        if (b > 0) {
          for (int p = 0; p < zero - lastzero; p++) {
            temp = (temp + dp[p][k - 1]) % 998244353;
          }
        }
        lastzero = 0;
        b = 1;
        ans = (998244353 + ans - temp) % 998244353;
        while (j < i) {
          if (s[j] == '1') {
            one--;
            j++;
            break;
          }
          j++;
          zero--;
        }
      }
      i++;
    }
    if (one == k) {
      for (int p = 0; p < zero; p++) {
        ans = (ans + dp[p][k]) % 998244353;
      }
      long long int temp = 0;
      if (b > 0) {
        for (int p = 0; p < zero - lastzero; p++) {
          temp = (temp + dp[p][k - 1]) % 998244353;
        }
      }
      ans = (998244353 + ans - temp) % 998244353;
    }
    cout << ans << "\n";
  }
  return 0;
}

### Prompt

Develop a solution in CPP 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;
long long int calculate(long long int p, long long int q) {
  long long int modx = 998244353, expo;
  expo = modx - 2;
  while (expo) {
    {
      if (expo & 1) p = (p * q) % modx;
    }
    q = (q * q) % modx;
    expo >>= 1;
  }
  return p % modx;
}
long long int power(long long int x, long long int y, long long int p) {
  long long int res = 1;
  x = x % p;
  if (x == 0) return 0;
  while (y > 0) {
    if (y & 1) {
      res = (res * x) % p;
    }
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  t = 1;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    string s;
    long long int ans = 1;
    cin >> s;
    if (k == 0) {
      cout << 1 << "\n";
      continue;
    }
    long long int i = 0, j = 0;
    long long int dp[n + 5][k + 5];
    memset(dp, 0, sizeof(dp));
    for (int p = 1; p <= k; p++) {
      dp[0][p] = dp[0][p - 1] + 1;
    }
    for (int p = 1; p <= n; p++) {
      for (int q = 1; q <= k; q++)
        dp[p][q] = (dp[p - 1][q] + dp[p][q - 1]) % 998244353;
    }
    long long int zero = 0, lastzero = 0, one = 0, b = 0;
    while (i < n) {
      if (s[i] == '0') {
        zero++;
        if (one == k) lastzero++;
      } else
        one++;
      if (one > k) {
        for (int p = 0; p < zero; p++) {
          ans = (ans + dp[p][k]) % 998244353;
        }
        long long int temp = 0;
        if (b > 0) {
          for (int p = 0; p < zero - lastzero; p++) {
            temp = (temp + dp[p][k - 1]) % 998244353;
          }
        }
        lastzero = 0;
        b = 1;
        ans = (998244353 + ans - temp) % 998244353;
        while (j < i) {
          if (s[j] == '1') {
            one--;
            j++;
            break;
          }
          j++;
          zero--;
        }
      }
      i++;
    }
    if (one == k) {
      for (int p = 0; p < zero; p++) {
        ans = (ans + dp[p][k]) % 998244353;
      }
      long long int temp = 0;
      if (b > 0) {
        for (int p = 0; p < zero - lastzero; p++) {
          temp = (temp + dp[p][k - 1]) % 998244353;
        }
      }
      ans = (998244353 + ans - temp) % 998244353;
    }
    cout << ans << "\n";
  }
  return 0;
}

```