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.
5 2
00011
 5 4
11011
 81 5
100000101000000011001101010100001010111000000110000000001000101101111000001000110
 4 3
1011
 47 25
11110011111001110100101010011000110111011011101
 291 159
011001110111110110001111000110001001111100010001011000110100110010001101100110111010101111100111110000110111001100111010001000011001010011011100101000101011010110010011010100100101111010111000001011110101001011101110100100111110011001101010001110110101010101100011101110111000011111011001110
 459 15
101010101010101010101010101010101010101010101111111111111111111111010101010101010101010101011111111111111111111101010101010101010101111111111111111111111101010101010101010111111111111111111111111101010101010101111111111111111111111111110110101010101011111111111111111111111111111001000111111111111111111111111111110000011111111111111111111111111111000001111111111111111111111111111100001111111111111111111111111111100111111111111111111111111111110111111111111
 105 58
110101000111100000011011011101110100001000110011010101100010111001011111010010111101011011010110011011110
 52 11
0110011111001000010000100010010001010100000100110100

10
 5
 187538
 4
 314445058
 1
 0
 132732930
 478323746

#include <bits/stdc++.h>
template <typename Sep, typename Head, typename... Tail>
void fold_print(Sep sep, Head&& h, Tail&&... args) {
  ((std::cerr << h) << ... << (std::cerr << sep, args));
}
std::mt19937_64 myrand(
    std::chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using LL = long long int;
void init();
void process();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T = 1;
  init();
  for (int t = 1; t <= T; t++) {
    process();
  }
  cout.flush();
  return 0;
}
constexpr LL MOD = 998244353;
vector<LL> fac(5000 * 2 + 1), inv(5000 * 2 + 1);
LL fastpw(LL x, LL p) {
  if (p == 0) return 1;
  LL tmp = fastpw(x * x % MOD, p / 2);
  if (p % 2 == 0)
    return tmp;
  else
    return tmp * x % MOD;
}
LL modinv(LL x) { return fastpw(x, MOD - 2); }
void init() {
  fac[0] = 1;
  for (LL i = 1; i < fac.size(); i++) {
    fac[i] = i * fac[i - 1] % MOD;
  }
  for (size_t i = 0; i < inv.size(); i++) {
    inv[i] = modinv(fac[i]);
  }
}
bool overlap(tuple<LL, LL> t1, tuple<LL, LL> t2) {
  auto [a, b] = t1;
  auto [c, d] = t2;
  a = max(a, c);
  b = min(b, d);
  return a <= b;
}
void process() {
  LL n, k;
  cin >> n >> k;
  vector<int> arr(n + 1, 0);
  {
    for (int i = 1; i <= n; i++) {
      char ch;
      cin >> ch;
      arr[i] = ch - '0';
    }
  }
  vector<int> sum(n + 1, 0);
  {
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i];
  }
  LL ans = 1;
  vector<tuple<LL, LL>> seg;
  LL l = 1, r = 1, cnt = (arr[1] == 1);
  while (r <= n) {
    if (r + 1 <= n && cnt < k) {
      if (arr[r + 1] == 1) {
        cnt += 1;
        r += 1;
        continue;
      }
    }
    if (r + 1 <= n && cnt == k) {
      if (arr[r + 1] == 0) {
        r += 1;
        continue;
      }
    }
    if (cnt != k) break;
    LL len = r - l + 1;
    LL one = cnt, zero = len - one;
    ans = (ans + MOD - 1 + fac[len] * inv[one] % MOD * inv[zero] % MOD) % MOD;
    if (!seg.empty()) {
      for (auto [prv_l, prv_r] : seg) {
        LL mx_l = max(prv_l, l), mn_r = min(prv_r, r);
        if (mn_r >= mx_l) {
          LL len = mn_r - mx_l + 1;
          LL one = sum[mn_r] - sum[mx_l - 1];
          LL zero = len - one;
          ans = (ans - fac[len] * inv[one] % MOD * inv[zero] % MOD + 1 + MOD) %
                MOD;
        }
      }
    }
    if (seg.empty() || !overlap(seg.back(), make_tuple(l, r))) {
      seg.emplace_back(l, r);
    } else {
      auto [u, v] = seg.back();
      seg.pop_back();
      seg.emplace_back(u, r);
    }
    while (cnt == k) {
      cnt -= (arr[l] == 1);
      l++;
    }
  }
  cout << ans << '\n';
}
