#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using uint = unsigned;
using ull = unsigned long long;
using umapII = unordered_map<int, int>;
using VI = vector<int>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VVVVB = vector<VVVB>;
using VVVVVB = vector<VVVVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VVVLL = vector<VVLL>;
using VVVVLL = vector<VVVLL>;
using VD = vector<db>;
using SI = set<int>;
using SS = set<string>;
using PII = pair<int, int>;
using PDD = pair<db, db>;
using PLL = pair<ll, ll>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VVVVI = vector<VVVI>;
using VVVVVI = vector<VVVVI>;
void eraseDups(VI& a) { a.erase(unique(a.begin(), a.end()), a.end()); }
int strToInt(string& a) {
  stringstream x(a);
  int b;
  x >> b;
  return b;
}
int bitCnt(int a) {
  bitset<64> b(a);
  return b.count();
}
int bitCnt(string a) {
  bitset<64> b(a);
  return b.count();
}
VI readVI(int n) {
  VI a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  return a;
}
VVI readVVI(int n, int m) {
  VVI a(n, VI(m));
  for (int i = 0; i < n; i++) a[i] = readVI(m);
  return a;
}
VLL readVLL(ll n) {
  VLL a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  return a;
}
VVLL readVVLL(ll n, ll m) {
  VVLL a(n, VLL(m));
  for (int i = 0; i < n; i++) a[i] = readVLL(m);
  return a;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void print(VI& a) {
  for (auto el : a) {
    cout << el << ' ';
  }
  cout << '\n';
}
void print(VPI& a) {
  for (auto el : a) {
    cout << el.first << ',' << el.second << ' ';
  }
  cout << '\n';
}
void print(VI& a, int n) {
  int cnt = 0;
  for (auto el : a) {
    if (cnt++ == n) break;
    cout << el << ' ';
  }
  cout << '\n';
}
void print(VVI& a) {
  for (auto el : a) {
    print(el);
  }
}
const int MOD1 = 1e9 + 7;
const int MOD = 998244353;
const int INF = 1.07e9;
const ll INFF = INT64_MAX;
const db EPS = 1e-9;
const db PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 5000;
ll fact[N + 5], invFact[N + 5];
ll power(ll a, int b) {
  ll ans = 1;
  while (b > 0) {
    if (b & 1) ans = (ans * a) % MOD;
    b >>= 1;
    a = (a * a) % MOD;
  }
  return ans;
}
ll inv(ll a, ll p) { return power(a, p - 2); }
ll nCr(ll a, ll b) {
  if (a < b || b < 0) return 0;
  if (b == 0 || a == b) return 1;
  return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
}
void init() {
  fact[0] = fact[1] = 1;
  for (int i = 2; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
  invFact[N] = inv(fact[N], MOD);
  for (int i = N - 1; i >= 0; i--)
    invFact[i] = invFact[i + 1] * ll(i + 1) % MOD;
}
ll n, k;
string s;
void go() {
  cin >> n >> k >> s;
  ll ans = 0;
  VI pos;
  for (int i = 0; i < n; i++)
    if (s[i] == '1') pos.push_back(i);
  if (k > pos.size() || k == 0) {
    cout << "1\n";
    return;
  }
  ll curLen = (pos.size() == k ? n : pos[k]), zero = 0;
  ans = (ans + nCr(curLen, k)) % MOD;
  for (int i = pos[k], j = -1; i < n; i++) {
    if (s[i] == '1') {
      curLen = i - pos[++j];
      zero = curLen - k;
      if (zero > 0) ans = (ans + nCr(curLen - 1, zero - 1)) % MOD;
    } else {
      curLen = i - pos[j];
      zero = curLen - k;
      ans = (ans + nCr(curLen - 1, k - 1)) % MOD;
    }
  }
  cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  init();
  while (T--) go();
  return (0 - 0);
}

### Prompt

Generate a CPP solution 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;
using ll = long long;
using db = double;
using uint = unsigned;
using ull = unsigned long long;
using umapII = unordered_map<int, int>;
using VI = vector<int>;
using VC = vector<char>;
using VS = vector<string>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VVVVB = vector<VVVB>;
using VVVVVB = vector<VVVVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VVVLL = vector<VVLL>;
using VVVVLL = vector<VVVLL>;
using VD = vector<db>;
using SI = set<int>;
using SS = set<string>;
using PII = pair<int, int>;
using PDD = pair<db, db>;
using PLL = pair<ll, ll>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VVVVI = vector<VVVI>;
using VVVVVI = vector<VVVVI>;
void eraseDups(VI& a) { a.erase(unique(a.begin(), a.end()), a.end()); }
int strToInt(string& a) {
  stringstream x(a);
  int b;
  x >> b;
  return b;
}
int bitCnt(int a) {
  bitset<64> b(a);
  return b.count();
}
int bitCnt(string a) {
  bitset<64> b(a);
  return b.count();
}
VI readVI(int n) {
  VI a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  return a;
}
VVI readVVI(int n, int m) {
  VVI a(n, VI(m));
  for (int i = 0; i < n; i++) a[i] = readVI(m);
  return a;
}
VLL readVLL(ll n) {
  VLL a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  return a;
}
VVLL readVVLL(ll n, ll m) {
  VVLL a(n, VLL(m));
  for (int i = 0; i < n; i++) a[i] = readVLL(m);
  return a;
}
int gcd(int a, int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void print(VI& a) {
  for (auto el : a) {
    cout << el << ' ';
  }
  cout << '\n';
}
void print(VPI& a) {
  for (auto el : a) {
    cout << el.first << ',' << el.second << ' ';
  }
  cout << '\n';
}
void print(VI& a, int n) {
  int cnt = 0;
  for (auto el : a) {
    if (cnt++ == n) break;
    cout << el << ' ';
  }
  cout << '\n';
}
void print(VVI& a) {
  for (auto el : a) {
    print(el);
  }
}
const int MOD1 = 1e9 + 7;
const int MOD = 998244353;
const int INF = 1.07e9;
const ll INFF = INT64_MAX;
const db EPS = 1e-9;
const db PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int N = 5000;
ll fact[N + 5], invFact[N + 5];
ll power(ll a, int b) {
  ll ans = 1;
  while (b > 0) {
    if (b & 1) ans = (ans * a) % MOD;
    b >>= 1;
    a = (a * a) % MOD;
  }
  return ans;
}
ll inv(ll a, ll p) { return power(a, p - 2); }
ll nCr(ll a, ll b) {
  if (a < b || b < 0) return 0;
  if (b == 0 || a == b) return 1;
  return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD;
}
void init() {
  fact[0] = fact[1] = 1;
  for (int i = 2; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
  invFact[N] = inv(fact[N], MOD);
  for (int i = N - 1; i >= 0; i--)
    invFact[i] = invFact[i + 1] * ll(i + 1) % MOD;
}
ll n, k;
string s;
void go() {
  cin >> n >> k >> s;
  ll ans = 0;
  VI pos;
  for (int i = 0; i < n; i++)
    if (s[i] == '1') pos.push_back(i);
  if (k > pos.size() || k == 0) {
    cout << "1\n";
    return;
  }
  ll curLen = (pos.size() == k ? n : pos[k]), zero = 0;
  ans = (ans + nCr(curLen, k)) % MOD;
  for (int i = pos[k], j = -1; i < n; i++) {
    if (s[i] == '1') {
      curLen = i - pos[++j];
      zero = curLen - k;
      if (zero > 0) ans = (ans + nCr(curLen - 1, zero - 1)) % MOD;
    } else {
      curLen = i - pos[j];
      zero = curLen - k;
      ans = (ans + nCr(curLen - 1, k - 1)) % MOD;
    }
  }
  cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T = 1;
  init();
  while (T--) go();
  return (0 - 0);
}

```