#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long double eps = 1e-9;
const long long mod = 998244353;
const int MAXN = 200000;
ll pow_mod(ll a, ll b, ll P) {
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % P;
    a = a * a % P;
    b >>= 1;
  }
  return ans;
}
ll inv_mod(ll a, ll P) { return pow_mod(a, P - 2ll, P); }
vector<ll> fact;
void calc_fact(int n, ll P) {
  if (fact.size() < 1) fact.push_back(1);
  for (int i = fact.size(), nnnn = (n + 1); i < nnnn; ++i)
    fact.push_back(fact[i - 1] * i % P);
}
vector<ll> fact_inv;
void calc_fact_inv(int n, ll P) {
  if (fact_inv.size() < 1) fact_inv.push_back(1);
  for (int i = fact_inv.size(), nnnn = (n + 1); i < nnnn; ++i)
    fact_inv.push_back(fact_inv[i - 1] * inv_mod(i, P) % P);
}
ll nCr(int n, int r, ll P) {
  if (r > n) return 0;
  calc_fact(n, P);
  calc_fact_inv(n, P);
  return (fact[n] * fact_inv[r] % P) * fact_inv[n - r] % P;
}
ll nCr_inv(int n, int r, ll P) {
  if (r > n) return 0;
  calc_fact(n, P);
  calc_fact_inv(n, P);
  return (fact_inv[n] * fact[r] % P) * fact[n - r] % P;
}
void solve() {
  ll n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  s = "1" + s + "1";
  int cur = -1;
  ll ans = 0;
  for (int i = 0, nnnn = (n + 2); i < nnnn; ++i) {
    if (s[i] == '1') {
      int j = i, cnt = 0, last = 0;
      while (j < n + 2) {
        if (s[j] == '1') {
          cnt++;
          if (j >= i + 2 && cnt == k + 2) {
            int num = cnt - 2;
            int spaces = j - 1 - i - 1 + 1;
            int calc;
            if (ans != 0)
              calc =
                  nCr(spaces, num, mod) - nCr(spaces - j + last, num - 1, mod);
            else
              calc = nCr(spaces, num, mod) - 1;
            if (calc < 0) calc += mod;
            ans += calc;
          }
          last = j;
        }
        if (cnt == k + 2) {
          break;
        }
        j++;
      }
    }
  }
  cout << (ans + 1) % mod << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << setprecision(12) << fixed;
  solve();
}

### Prompt

Your task is to create a CPP solution to the following problem:

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;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long double eps = 1e-9;
const long long mod = 998244353;
const int MAXN = 200000;
ll pow_mod(ll a, ll b, ll P) {
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % P;
    a = a * a % P;
    b >>= 1;
  }
  return ans;
}
ll inv_mod(ll a, ll P) { return pow_mod(a, P - 2ll, P); }
vector<ll> fact;
void calc_fact(int n, ll P) {
  if (fact.size() < 1) fact.push_back(1);
  for (int i = fact.size(), nnnn = (n + 1); i < nnnn; ++i)
    fact.push_back(fact[i - 1] * i % P);
}
vector<ll> fact_inv;
void calc_fact_inv(int n, ll P) {
  if (fact_inv.size() < 1) fact_inv.push_back(1);
  for (int i = fact_inv.size(), nnnn = (n + 1); i < nnnn; ++i)
    fact_inv.push_back(fact_inv[i - 1] * inv_mod(i, P) % P);
}
ll nCr(int n, int r, ll P) {
  if (r > n) return 0;
  calc_fact(n, P);
  calc_fact_inv(n, P);
  return (fact[n] * fact_inv[r] % P) * fact_inv[n - r] % P;
}
ll nCr_inv(int n, int r, ll P) {
  if (r > n) return 0;
  calc_fact(n, P);
  calc_fact_inv(n, P);
  return (fact_inv[n] * fact[r] % P) * fact[n - r] % P;
}
void solve() {
  ll n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  s = "1" + s + "1";
  int cur = -1;
  ll ans = 0;
  for (int i = 0, nnnn = (n + 2); i < nnnn; ++i) {
    if (s[i] == '1') {
      int j = i, cnt = 0, last = 0;
      while (j < n + 2) {
        if (s[j] == '1') {
          cnt++;
          if (j >= i + 2 && cnt == k + 2) {
            int num = cnt - 2;
            int spaces = j - 1 - i - 1 + 1;
            int calc;
            if (ans != 0)
              calc =
                  nCr(spaces, num, mod) - nCr(spaces - j + last, num - 1, mod);
            else
              calc = nCr(spaces, num, mod) - 1;
            if (calc < 0) calc += mod;
            ans += calc;
          }
          last = j;
        }
        if (cnt == k + 2) {
          break;
        }
        j++;
      }
    }
  }
  cout << (ans + 1) % mod << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << setprecision(12) << fixed;
  solve();
}

```