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 <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;
  }
  