#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(unsigned long long &x) { scanf("%llu", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
const int MOD = 998244353, mod = 998244353;
long long qpow(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
const int MAXN = 4e5 + 10, MAXM = 1e7 + 10;
const int INF = INT_MAX, SINF = 0x3f3f3f3f;
const long long llINF = LLONG_MAX;
const int inv2 = (MOD + 1) / 2;
const int Lim = 1 << 20;
template <int _P>
struct Modint {
  static constexpr int P = _P;

 private:
  int v;

 public:
  Modint() : v(0) {}
  Modint(long long _v) {
    v = _v % P;
    if (v < 0) v += P;
  }
  explicit operator int() const { return v; }
  explicit operator long long() const { return v; }
  explicit operator bool() const { return v > 0; }
  bool operator==(const Modint &o) const { return v == o.v; }
  bool operator!=(const Modint &o) const { return v != o.v; }
  Modint operator-() const { return Modint(v ? P - v : 0); }
  Modint operator+() const { return *this; }
  Modint &operator++() {
    v++;
    if (v == P) v = 0;
    return *this;
  }
  Modint &operator--() {
    if (v == 0) v = P;
    v--;
    return *this;
  }
  Modint operator++(int) {
    Modint r = *this;
    ++*this;
    return r;
  }
  Modint operator--(int) {
    Modint r = *this;
    --*this;
    return r;
  }
  Modint &operator+=(const Modint &o) {
    v += o.v;
    if (v >= P) v -= P;
    return *this;
  }
  Modint operator+(const Modint &o) const { return Modint(*this) += o; }
  Modint &operator-=(const Modint &o) {
    v -= o.v;
    if (v < 0) v += P;
    return *this;
  }
  Modint operator-(const Modint &o) const { return Modint(*this) -= o; }
  Modint &operator*=(const Modint &o) {
    v = (int)(((long long)v) * o.v % P);
    return *this;
  }
  Modint operator*(const Modint &o) const { return Modint(*this) *= o; }
  Modint &operator/=(const Modint &o) { return (*this) *= o.Inv(); }
  Modint operator/(const Modint &o) const { return Modint(*this) /= o; }
  friend Modint operator+(const Modint &x, const long long &o) {
    return x + (Modint)o;
  }
  friend Modint operator+(const long long &o, const Modint &x) {
    return x + (Modint)o;
  }
  friend Modint operator-(const Modint &x, const long long &o) {
    return x - (Modint)o;
  }
  friend Modint operator-(const long long &o, const Modint &x) {
    return (Modint)o - x;
  }
  friend Modint operator*(const Modint &x, const long long &o) {
    return x * (Modint)o;
  }
  friend Modint operator*(const long long &o, const Modint &x) {
    return x * (Modint)o;
  }
  friend Modint operator/(const Modint &x, const long long &o) {
    Modint c = o;
    return x * c.Inv();
  }
  friend Modint operator/(const long long &o, const Modint &x) {
    Modint c = o;
    return c * x.Inv();
  }
  Modint operator^(long long o) const {
    Modint r = 1, t = v;
    while (o) {
      if (o & 1) r *= t;
      t *= t;
      o >>= 1;
    }
    return r;
  }
  Modint operator~() { return (*this) ^ (P - 2); }
  Modint Inv() const { return (*this) ^ (P - 2); }
};
using mi = Modint<MOD>;
template <int P>
void _W(Modint<P> x) {
  printf("%d", (int)x);
}
template <int P>
void _R(Modint<P> &x) {
  long long t;
  scanf("%lld", &t);
  x = t;
}
mi fac[MAXN], inc[MAXN];
void fac_pre(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
  inc[n] = ~fac[n];
  for (int i = n; i; i--) inc[i - 1] = inc[i] * i;
}
mi c(int di, int gao) {
  if (di < gao || gao < 0 || di < 0) return 0;
  return fac[di] * inc[gao] * inc[di - gao];
}
int n, k;
char s[MAXN];
mi ans[5005][5005];
int sum[MAXN];
void solve() {
  R(n, k, s);
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i - 1] == '1');
  if (k > sum[n]) return W(1);
  mi res = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      if (sum[j] - sum[i - 1]) {
        if (sum[j] - sum[i - 1] > k) continue;
        ans[i][j] = c(j - i + 1, sum[j] - sum[i - 1]);
      }
  for (int i = 1; i <= n; i++)
    for (int j = n; j >= i; j--) {
      if (sum[j] - sum[i - 1] > k) continue;
      ans[i][j] -= ans[i][j - 1];
      ans[i][j] -= ans[i + 1][j];
      ans[i][j] += ans[i + 1][j - 1];
      res += ans[i][j];
    }
  if (k == 1) res -= (sum[n] - 1);
  if (k == 0) res = 1;
  W(res);
}
int main() {
  fac_pre(5555);
  int T = 1;
  for (int kase = 1; kase <= T; kase++) {
    solve();
  }
  return 0;
}

### Prompt

Please formulate 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 <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(unsigned long long &x) { scanf("%llu", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
const int MOD = 998244353, mod = 998244353;
long long qpow(long long a, long long b) {
  long long res = 1;
  a %= MOD;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
  }
  return res;
}
const int MAXN = 4e5 + 10, MAXM = 1e7 + 10;
const int INF = INT_MAX, SINF = 0x3f3f3f3f;
const long long llINF = LLONG_MAX;
const int inv2 = (MOD + 1) / 2;
const int Lim = 1 << 20;
template <int _P>
struct Modint {
  static constexpr int P = _P;

 private:
  int v;

 public:
  Modint() : v(0) {}
  Modint(long long _v) {
    v = _v % P;
    if (v < 0) v += P;
  }
  explicit operator int() const { return v; }
  explicit operator long long() const { return v; }
  explicit operator bool() const { return v > 0; }
  bool operator==(const Modint &o) const { return v == o.v; }
  bool operator!=(const Modint &o) const { return v != o.v; }
  Modint operator-() const { return Modint(v ? P - v : 0); }
  Modint operator+() const { return *this; }
  Modint &operator++() {
    v++;
    if (v == P) v = 0;
    return *this;
  }
  Modint &operator--() {
    if (v == 0) v = P;
    v--;
    return *this;
  }
  Modint operator++(int) {
    Modint r = *this;
    ++*this;
    return r;
  }
  Modint operator--(int) {
    Modint r = *this;
    --*this;
    return r;
  }
  Modint &operator+=(const Modint &o) {
    v += o.v;
    if (v >= P) v -= P;
    return *this;
  }
  Modint operator+(const Modint &o) const { return Modint(*this) += o; }
  Modint &operator-=(const Modint &o) {
    v -= o.v;
    if (v < 0) v += P;
    return *this;
  }
  Modint operator-(const Modint &o) const { return Modint(*this) -= o; }
  Modint &operator*=(const Modint &o) {
    v = (int)(((long long)v) * o.v % P);
    return *this;
  }
  Modint operator*(const Modint &o) const { return Modint(*this) *= o; }
  Modint &operator/=(const Modint &o) { return (*this) *= o.Inv(); }
  Modint operator/(const Modint &o) const { return Modint(*this) /= o; }
  friend Modint operator+(const Modint &x, const long long &o) {
    return x + (Modint)o;
  }
  friend Modint operator+(const long long &o, const Modint &x) {
    return x + (Modint)o;
  }
  friend Modint operator-(const Modint &x, const long long &o) {
    return x - (Modint)o;
  }
  friend Modint operator-(const long long &o, const Modint &x) {
    return (Modint)o - x;
  }
  friend Modint operator*(const Modint &x, const long long &o) {
    return x * (Modint)o;
  }
  friend Modint operator*(const long long &o, const Modint &x) {
    return x * (Modint)o;
  }
  friend Modint operator/(const Modint &x, const long long &o) {
    Modint c = o;
    return x * c.Inv();
  }
  friend Modint operator/(const long long &o, const Modint &x) {
    Modint c = o;
    return c * x.Inv();
  }
  Modint operator^(long long o) const {
    Modint r = 1, t = v;
    while (o) {
      if (o & 1) r *= t;
      t *= t;
      o >>= 1;
    }
    return r;
  }
  Modint operator~() { return (*this) ^ (P - 2); }
  Modint Inv() const { return (*this) ^ (P - 2); }
};
using mi = Modint<MOD>;
template <int P>
void _W(Modint<P> x) {
  printf("%d", (int)x);
}
template <int P>
void _R(Modint<P> &x) {
  long long t;
  scanf("%lld", &t);
  x = t;
}
mi fac[MAXN], inc[MAXN];
void fac_pre(int n) {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
  inc[n] = ~fac[n];
  for (int i = n; i; i--) inc[i - 1] = inc[i] * i;
}
mi c(int di, int gao) {
  if (di < gao || gao < 0 || di < 0) return 0;
  return fac[di] * inc[gao] * inc[di - gao];
}
int n, k;
char s[MAXN];
mi ans[5005][5005];
int sum[MAXN];
void solve() {
  R(n, k, s);
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i - 1] == '1');
  if (k > sum[n]) return W(1);
  mi res = 0;
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      if (sum[j] - sum[i - 1]) {
        if (sum[j] - sum[i - 1] > k) continue;
        ans[i][j] = c(j - i + 1, sum[j] - sum[i - 1]);
      }
  for (int i = 1; i <= n; i++)
    for (int j = n; j >= i; j--) {
      if (sum[j] - sum[i - 1] > k) continue;
      ans[i][j] -= ans[i][j - 1];
      ans[i][j] -= ans[i + 1][j];
      ans[i][j] += ans[i + 1][j - 1];
      res += ans[i][j];
    }
  if (k == 1) res -= (sum[n] - 1);
  if (k == 0) res = 1;
  W(res);
}
int main() {
  fac_pre(5555);
  int T = 1;
  for (int kase = 1; kase <= T; kase++) {
    solve();
  }
  return 0;
}

```