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;
  long long mod = 998244353;
  long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  long long mod_add(long long a, long long b) {
    a = a % mod;
    b = b % mod;
    return (((a + b) % mod) + mod) % mod;
  }
  long long mod_mul(long long a, long long b) {
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
  }
  long long inv(long long i) {
    if (i == 1) return 1;
    return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;
  }
  long long maxn = 5001;
  vector<long long> fact(maxn, 1);
  vector<long long> ifact(maxn, 1);
  void calFact() {
    for (long long i = 2; i < maxn; i++) fact[i] = mod_mul(fact[i - 1], i);
  }
  long long ncr(long long n, long long r) {
    long long ans = fact[n];
    ans = mod_mul(ans, inv(fact[n - r]));
    ans = mod_mul(ans, inv(fact[r]));
    return ans;
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    calFact();
    long long n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<long long> dp(n, 0);
    dp[0] = 1;
    bool first = false;
    for (long long i = 1; i < n; i++) {
      long long ones = 0, zeroes = 0;
      dp[i] = dp[i - 1];
      for (long long j = i; j >= 0; j--) {
        if (s[j] == '1') {
          if (ones == k) break;
          ones++;
        } else
          zeroes++;
      }
      if (ones < k) continue;
      long long temp;
      if (first == false) {
        temp = (ncr(zeroes + ones, zeroes) - 1 + mod) % mod;
      } else {
        if (s[i] == '1') {
          temp = 0;
          if (zeroes > 0) {
            temp = ncr(zeroes + ones - 1, zeroes - 1);
          }
        } else {
          temp = 0;
          if (ones > 0) {
            temp = ncr(zeroes + ones - 1, zeroes);
          }
        }
      }
      first = true;
      dp[i] = mod_add(dp[i], temp);
    }
    cout << dp[n - 1] << "\n";
  }
  