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;
  const int maxn = 10005;
  char buffer[maxn], *S, *T;
  inline char Get_Char() {
    if (S == T) {
      T = (S = buffer) + fread(buffer, 1, maxn, stdin);
      if (S == T) return EOF;
    }
    return *S++;
  }
  inline int read() {
    register char c;
    register int re = 0, f = 0;
    for (c = Get_Char(); c < '0' or c > '9'; c = Get_Char())
      if (c == '-') f = 1;
    for (; c >= '0' and c <= '9';)
      re = (re << 1) + (re << 3) + (c - '0'), c = Get_Char();
    if (f) return -re;
    return re;
  }
  inline void read(int& x) {
    register char c;
    register int re = 0, f = 0;
    for (c = Get_Char(); c < '0' or c > '9'; c = Get_Char())
      if (c == '-') f = 1;
    for (; c >= '0' and c <= '9';)
      re = (re << 1) + (re << 3) + (c - '0'), c = Get_Char();
    if (f)
      x = -re;
    else
      x = re;
  }
  inline void read(long long& x) {
    register char c;
    register long long re = 0, f = 0;
    for (c = Get_Char(); c < '0' or c > '9'; c = Get_Char())
      if (c == '-') f = 1;
    for (; c >= '0' and c <= '9';)
      re = (re << 1) + (re << 3) + (c - '0'), c = Get_Char();
    if (f)
      x = -re;
    else
      x = re;
  }
  const int mxn = 5005;
  const int md = 998244353;
  long long c[mxn][mxn], n, k;
  string s;
  inline void solve() {
    c[0][0] = 1;
    c[1][0] = c[1][1] = 1;
    for (int i = 2; i < mxn; ++i) {
      c[i][0] = 1;
      for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % md;
    }
    cin >> n >> k >> s;
    int cc = 0;
    s = " " + s;
    for (int i = 1; i <= n; ++i)
      if (s[i] == '1') ++cc;
    if (cc == k) {
      cout << c[n][k] << '\n';
      return;
    }
    bool fst = 1;
    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
      if (s[i] != '1') continue;
      int cnt = 0;
      int j = i;
      for (; j <= n; ++j) {
        if (s[j] == '1') ++cnt;
        if (cnt == k) break;
      }
      if (j == n + 1) break;
      if (cnt < k) break;
      int ti = i - 1, tj = j + 1;
      for (; ti and s[ti] == '0';) --ti;
      for (; tj <= n and s[tj] == '0';) ++tj;
      ++ti, --tj;
      for (int tk = tj; tk >= ti; --tk) {
        if (tk == j) continue;
        ans += c[tk - ti][k - 1];
        ans %= md;
      }
      if (fst) {
        fst = 0;
        ans += c[j - 1][k - 1] - 1;
        ans %= md;
        if (ans < 0) ans += md;
      }
    }
    (ans += 1) %= md;
    cout << ans << '\n';
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    for (; T--;) solve();
    return 0;
  }
  