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;
  void __print(int x) { cerr << x; }
  void __print(long x) { cerr << x; }
  void __print(long long x) { cerr << x; }
  void __print(unsigned x) { cerr << x; }
  void __print(unsigned long x) { cerr << x; }
  void __print(unsigned long long x) { cerr << x; }
  void __print(float x) { cerr << x; }
  void __print(double x) { cerr << x; }
  void __print(long double x) { cerr << x; }
  void __print(char x) { cerr << '\'' << x << '\''; }
  void __print(const char *x) { cerr << '\"' << x << '\"'; }
  void __print(const string &x) { cerr << '\"' << x << '\"'; }
  void __print(bool x) { cerr << (x ? "true" : "false"); }
  template <typename T, typename V>
  void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
  }
  template <typename T>
  void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
  }
  void _print() { cerr << "]\n"; }
  template <typename T, typename... V>
  void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
  }
  template <typename T>
  void Print(T a[], T n) {
    for (int i = 0; i < n; i++) {
      cout << a[i] << " ";
    }
    cout << endl;
  }
  const long long int N = 5005;
  const long long int M = 998244353;
  long long int fact[N], inv[N];
  long long int power(long long int a, long long int b, long long int M) {
    long long int ans = 1;
    while (b) {
      if (b % 2 != 0) {
        ans *= a;
      }
      ans %= M;
      a *= a;
      a %= M;
      b /= 2;
    }
    return ans;
  }
  void fun() {
    fact[0] = 1;
    inv[0] = 1;
    for (long long int i = 1; i < N; i++) {
      fact[i] = fact[i - 1] * i;
      fact[i] %= M;
      inv[i] = power(fact[i], M - 2, M);
    }
  }
  long long int ncr(long long int n, long long int r) {
    long long int ans = fact[n] * inv[r];
    ans %= M;
    ans *= inv[n - r];
    return ans % M;
  }
  void solve() {
    long long int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (count(s.begin(), s.end(), '1') < k) {
      cout << 1 << "\n";
      return;
    }
    if (count(s.begin(), s.end(), '1') == n) {
      cout << 1 << "\n";
      return;
    }
    if (k == 0) {
      cout << 1 << "\n";
      return;
    }
    long long int z = 0, o = 0;
    long long int ans = 0;
    long long int flag = 0;
    long long int overlap[n];
    fill(overlap, overlap + n, 0);
    long long int j = 0;
    for (long long int i = 0; i < n; i++) {
      z += s[i] == '0';
      o += s[i] == '1';
      if (o > k) {
        while (o > k && j < i) {
          o -= s[j] == '1';
          z -= s[j] == '0';
          j++;
        }
      }
      if (o == k && z > 0) {
        if (overlap[j] == 1) {
          if (s[i] == '0') {
            ans += ncr(o + z - 1, z);
            ans %= M;
          } else {
            ans += ncr(o + z - 1, o);
            ans %= M;
          }
          fill(overlap + j, overlap + i + 1, 1);
          continue;
        }
        fill(overlap + j, overlap + i + 1, 1);
        if (flag == 0)
          ans += ncr(z + o, o), flag = 1;
        else
          ans += ncr(z + o, o) - 1;
        ans %= M;
      }
    }
    cout << ans << "\n";
  }
  signed main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    fun();
    solve();
  }
  