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 long long inf = 1e18;
  template <long long MOD>
  struct ModInt {
    long long v;
    ModInt(long long _v = 0) {
      v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
      if (v < 0) v += MOD;
    }
    ModInt &operator+=(const ModInt &other) {
      v += other.v;
      if (v >= MOD) v -= MOD;
      return *this;
    }
    ModInt &operator-=(const ModInt &other) {
      v -= other.v;
      if (v < 0) v += MOD;
      return *this;
    }
    ModInt &operator*=(const ModInt &other) {
      v = v * other.v % MOD;
      return *this;
    }
    ModInt &operator/=(const ModInt &other) { return *this *= inverse(other); }
    bool operator==(const ModInt &other) const { return v == other.v; }
    bool operator!=(const ModInt &other) const { return v != other.v; }
    friend ModInt operator+(ModInt a, const ModInt &b) { return a += b; }
    friend ModInt operator-(ModInt a, const ModInt &b) { return a -= b; }
    friend ModInt operator*(ModInt a, const ModInt &b) { return a *= b; }
    friend ModInt operator/(ModInt a, const ModInt &b) { return a /= b; }
    friend ModInt operator-(const ModInt &a) { return 0 - a; }
    friend ModInt power(ModInt a, long long b) {
      ModInt ret(1);
      while (b > 0) {
        if (b & 1) ret *= a;
        a *= a;
        b >>= 1;
      }
      return ret;
    }
    friend ModInt inverse(ModInt a) { return power(a, MOD - 2); }
    friend istream &operator>>(istream &is, ModInt &m) {
      is >> m.v;
      m.v = (-MOD < m.v && m.v < MOD) ? m.v : m.v % MOD;
      if (m.v < 0) m.v += MOD;
      return is;
    }
    friend ostream &operator<<(ostream &os, const ModInt &m) { return os << m.v; }
  };
  const long long mod = 998244353;
  signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n, k;
    string str;
    cin >> n >> k >> str;
    vector<long long> prefix(n + 1);
    prefix[0] = 0;
    for (long long x = 0; x < n; x++) {
      prefix[x + 1] = prefix[x] + (str[x] == '1');
    }
    vector<ModInt<mod> > factorials(n + 1);
    factorials[0] = 1;
    for (long long x = 1; x <= n; x++) {
      factorials[x] = (factorials[x - 1] * x);
    }
    map<pair<long long, long long>, long long> map3;
    ModInt<mod> total = 0;
    for (long long x = 0; x < n; x++) {
      for (long long y = x + 1; y < n; y++) {
        long long ones = prefix[y + 1] - prefix[x];
        long long zeros = y - x + 1 - ones;
        if (ones <= k) {
          if (str[x] == '1') {
            zeros--;
          }
          if (str[x] == '0') {
            ones--;
          }
          if (str[y] == '1') {
            zeros--;
          }
          if (str[y] == '0') {
            ones--;
          }
          if (ones >= 0 && zeros >= 0) {
            if (zeros < ones) {
              swap(zeros, ones);
            }
            map3[make_pair(zeros, ones)]++;
          }
        }
      }
    }
    while (map3.size() > 0) {
      pair<pair<long long, long long>, long long> curr = *map3.begin();
      total += curr.second * factorials[curr.first.first + curr.first.second] /
               factorials[curr.first.first] / factorials[curr.first.second];
      map3.erase(curr.first);
    }
    if (prefix[n] < k) {
      total = 0;
    }
    total += 1;
    cout << total << "\n";
    return 0;
  }
  