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 <int64_t mod>
  struct ModInt {
    int64_t x;
    ModInt() : x(0) {}
    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) {
      if ((x += p.x) >= mod) x -= mod;
      return *this;
    }
    ModInt &operator-=(const ModInt &p) {
      if ((x += mod - p.x) >= mod) x -= mod;
      return *this;
    }
    ModInt &operator*=(const ModInt &p) {
      x = int64_t(int64_t(1) * x * p.x % mod);
      return *this;
    }
    ModInt &operator/=(const ModInt &p) {
      *this *= p.inverse();
      return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const {
      int64_t a = x, b = mod, u = 1, v = 0, t;
      while (b > 0) {
        t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
      }
      return ModInt(u);
    }
    ModInt power(int64_t n) const {
      ModInt ret(1), mul(x);
      while (n > 0) {
        if (n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
      }
      return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
    friend istream &operator>>(istream &is, ModInt &a) {
      int64_t t;
      is >> t;
      a = ModInt<mod>(t);
      return (is);
    }
    static int64_t get_mod() { return mod; }
  };
  const int64_t mod = 998244353;
  using Mint = ModInt<mod>;
  int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int64_t n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (k == 0) {
      cout << "1\n";
      return 0;
    }
    vector<vector<Mint>> choose(n + 1, vector<Mint>(n + 1));
    for (int64_t i = 0; i <= n; i++) {
      for (int64_t j = 0; j <= i; j++) {
        if (i == 0 || j == 0)
          choose[i][j] = 1;
        else
          choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];
      }
    }
    vector<int64_t> a;
    for (int64_t i = 0; i < n; i++) {
      if (s[i] == '1') {
        a.push_back(i);
      }
    }
    if (int64_t(a.size()) < k) {
      cout << 1;
      return 0;
    }
    a.insert(a.begin(), -1);
    a.push_back(n);
    ;
    Mint ans = 0;
    for (int64_t i = 1; i + k - 1 <= int64_t(a.size()) - 2; i++) {
      int64_t l = a[i], r = a[i + k - 1];
      int64_t L = a[i - 1] + 1, R = a[i + k] - 1;
      ;
      ;
      ans += choose[R - L + 1][k];
      if (i + k - 1 < int64_t(a.size()) - 2) {
        ans -= choose[R - l][k - 1];
      };
    }
    cout << ans;
    return 0;
  }
  