#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  if (v.size() == 0) {
    os << "empty vector\n";
    return os;
  }
  for (auto element : v) os << element << " ";
  return os;
}
template <typename T, typename second>
ostream& operator<<(ostream& os, pair<T, second>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T>& v) {
  if (v.size() == 0) {
    os << "empty set\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "[";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << *it;
    if (it != endit) os << ", ";
  }
  os << "]";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, multiset<T>& v) {
  if (v.size() == 0) {
    os << "empty multiset\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "[";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << *it;
    if (it != endit) os << ", ";
  }
  os << "]";
  return os;
}
template <typename T, typename second>
ostream& operator<<(ostream& os, map<T, second>& v) {
  if (v.size() == 0) {
    os << "empty map\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << "(" << (*it).first << " : " << (*it).second << ")";
    if (it != endit) os << ", ";
  }
  os << "}";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<vector<T>>& v) {
  for (auto& subv : v) {
    for (auto& e : subv) os << e << " ";
    os << "\n";
  }
  return os;
}
bool do_debug = false;
long long n, k;
vector<long long> v;
vector<long long> fact(50010), ifact(50010);
long long power(long long x, long long n) {
  if (!n) return 1;
  if (n % 2)
    return (x * (power((x * x) % 998244353, n / 2) % 998244353)) % 998244353;
  return power((x * x) % 998244353, n / 2) % 998244353;
}
long long inverse(long long n) {
  return power(fact[n], 998244353 - 2) % 998244353;
}
void pre_factorials() {
  fact[0] = 1;
  for (long long i = 1; i < 50010; i++) fact[i] = (fact[i - 1] * i) % 998244353;
  for (long long i = 0; i < 50010; i++) ifact[i] = inverse(i);
}
long long ncr(long long n, long long r) {
  if (n < r)
    return 0;
  else if (n == r)
    return 1;
  else if (r == 0)
    return 0;
  long long ans = fact[n];
  ans = (ans * ifact[r]) % 998244353;
  ans = (ans * ifact[n - r]) % 998244353;
  return ans;
}
vector<vector<long long>> ps(5010, vector<long long>(2));
long long cal(long long left, long long right) {
  long long len = right - left + 1;
  long long zero = ps[right][0] - ps[left - 1][0];
  long long one = len - zero;
  long long ans = fact[len];
  ans *= (ifact[one]);
  ans %= 998244353;
  ans *= (ifact[zero]);
  ans %= 998244353;
  return ans;
}
void Runtime_Terror() {
  cin >> n >> k;
  string s;
  cin >> s;
  vector<long long> one;
  one.push_back(0);
  for (long long i = 0; i < s.size(); i++) {
    if (s[i] == '1') one.push_back(i + 1);
    ps[i + 1] = ps[i];
    if (s[i] == '1')
      ps[i + 1][1]++;
    else
      ps[i + 1][0]++;
  }
  one.push_back(n + 1);
  long long sz = one.size() - 2;
  if (sz < k || k == 0) {
    cout << 1 << "\n";
    return;
  };
  ;
  long long ans = 0;
  for (long long i = 1; i < sz - k + 2; i++) {
    long long left = one[i - 1] + 1;
    long long right = one[i + k] - 1;
    ans += cal(left, right);
    ans %= 998244353;
    if (i != sz - k + 1) {
      long long tem = cal(one[i] + 1, one[i + k] - 1);
      ans = (((ans - tem) % 998244353) + 998244353) % 998244353;
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  pre_factorials();
  for (long long i = 0; i < t; i++) Runtime_Terror();
  return 0;
}

### 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;
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  if (v.size() == 0) {
    os << "empty vector\n";
    return os;
  }
  for (auto element : v) os << element << " ";
  return os;
}
template <typename T, typename second>
ostream& operator<<(ostream& os, pair<T, second>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, set<T>& v) {
  if (v.size() == 0) {
    os << "empty set\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "[";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << *it;
    if (it != endit) os << ", ";
  }
  os << "]";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, multiset<T>& v) {
  if (v.size() == 0) {
    os << "empty multiset\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "[";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << *it;
    if (it != endit) os << ", ";
  }
  os << "]";
  return os;
}
template <typename T, typename second>
ostream& operator<<(ostream& os, map<T, second>& v) {
  if (v.size() == 0) {
    os << "empty map\n";
    return os;
  }
  auto endit = v.end();
  endit--;
  os << "{";
  for (auto it = v.begin(); it != v.end(); it++) {
    os << "(" << (*it).first << " : " << (*it).second << ")";
    if (it != endit) os << ", ";
  }
  os << "}";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<vector<T>>& v) {
  for (auto& subv : v) {
    for (auto& e : subv) os << e << " ";
    os << "\n";
  }
  return os;
}
bool do_debug = false;
long long n, k;
vector<long long> v;
vector<long long> fact(50010), ifact(50010);
long long power(long long x, long long n) {
  if (!n) return 1;
  if (n % 2)
    return (x * (power((x * x) % 998244353, n / 2) % 998244353)) % 998244353;
  return power((x * x) % 998244353, n / 2) % 998244353;
}
long long inverse(long long n) {
  return power(fact[n], 998244353 - 2) % 998244353;
}
void pre_factorials() {
  fact[0] = 1;
  for (long long i = 1; i < 50010; i++) fact[i] = (fact[i - 1] * i) % 998244353;
  for (long long i = 0; i < 50010; i++) ifact[i] = inverse(i);
}
long long ncr(long long n, long long r) {
  if (n < r)
    return 0;
  else if (n == r)
    return 1;
  else if (r == 0)
    return 0;
  long long ans = fact[n];
  ans = (ans * ifact[r]) % 998244353;
  ans = (ans * ifact[n - r]) % 998244353;
  return ans;
}
vector<vector<long long>> ps(5010, vector<long long>(2));
long long cal(long long left, long long right) {
  long long len = right - left + 1;
  long long zero = ps[right][0] - ps[left - 1][0];
  long long one = len - zero;
  long long ans = fact[len];
  ans *= (ifact[one]);
  ans %= 998244353;
  ans *= (ifact[zero]);
  ans %= 998244353;
  return ans;
}
void Runtime_Terror() {
  cin >> n >> k;
  string s;
  cin >> s;
  vector<long long> one;
  one.push_back(0);
  for (long long i = 0; i < s.size(); i++) {
    if (s[i] == '1') one.push_back(i + 1);
    ps[i + 1] = ps[i];
    if (s[i] == '1')
      ps[i + 1][1]++;
    else
      ps[i + 1][0]++;
  }
  one.push_back(n + 1);
  long long sz = one.size() - 2;
  if (sz < k || k == 0) {
    cout << 1 << "\n";
    return;
  };
  ;
  long long ans = 0;
  for (long long i = 1; i < sz - k + 2; i++) {
    long long left = one[i - 1] + 1;
    long long right = one[i + k] - 1;
    ans += cal(left, right);
    ans %= 998244353;
    if (i != sz - k + 1) {
      long long tem = cal(one[i] + 1, one[i + k] - 1);
      ans = (((ans - tem) % 998244353) + 998244353) % 998244353;
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  pre_factorials();
  for (long long i = 0; i < t; i++) Runtime_Terror();
  return 0;
}

```