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

### Prompt

Please create a solution in CPP to the following problem:

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.

### Response

```cpp
#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;
}

```