description: 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.
solution: #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;
  }
  