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

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define vs vector<string>
#define pb push_back
#define ll long long
#define log(args...) 	{ string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define logarr(arr,a,b)	for(int z=(a);z<=(b);z++) cout<<(arr[z])<<" ";cout<<endl;
vs tokenizer(string str, char ch) {std::istringstream var((str)); vs v; string t; while (getline((var), t, (ch))) {v.pb(t);} return v;}
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}
#define MOD 998244353
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
ll modpow(ll x, ll n, ll m)
{
	if (n == 0) return 1 % m;
	ll u = modpow(x, n / 2, m);
	u = (u * u) % m;
	if (n % 2 == 1) u = (u * x) % m;
	return u;
}
ll powerRecursive(ll a, ll b)
{
	//base case
	if (b == 0)return 1;
	if (b == 1)return a;
	ll temp = powerRecursive(a, b / 2);
	if (b % 2 == 0)
		return temp * temp;
	else
		return a * temp * temp;
}
ll CEIL(ll a, ll b)
{
	if (a % b == 0)
		return a / b;
	return a / b + 1;
}
ll power(ll x, ll y, ll p)
{
	ll res = 1;
	x = x % p;
	while (y > 0)
	{
		if (y & 1)
			res = (res * x) % p;
		y = y >> 1;
		x = (x * x) % p;
	}
	return res;
}
ll modInverse(ll n, ll p)
{
	return power(n, p - 2, p);
}
ll nCrModPFermat(ll n, ll r, ll p)
{
	if (n < r)
		return 0;
	if (r == 0)
		return 1;
	ll fac[n + 1];
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = (fac[i - 1] * i) % p;
	return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}
int main()
{
	clock_t begin = clock();
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n, k;
	cin >> n >> k;
	vector<ll> ans(n, 0);
	string s;
	cin >> s;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == '0')
		{
			int cnt = 0, len = 0, flag = 0;
			for (int j = i - 1; j >= 0; j--)
			{
				if (s[j] == '1')
					cnt++;
				len++;
				if (cnt == k + 1)
				{
					flag = 1;
					break;
				}
			}
			if (cnt == k)
				len++;
			if (flag == 1 or cnt == k)
				ans[i] = (ans[i - 1] + (nCrModPFermat(len, k, MOD) - nCrModPFermat(len - 1, k, MOD) + MOD) % MOD) % MOD;
			else
				ans[i] = ans[i - 1];
		}
		else
		{
			int cnt = 0, len = 0, flag = 0, zeros;
			for (int j = i - 1; j >= 0; j--)
			{
				if (s[j] == '1')
					cnt++;
				len++;
				if (cnt == k)
				{
					flag = 1;
					break;
				}
			}
			zeros = len - k;
			//log(cnt, flag, len, zeros);
			if (flag == 1 and zeros >= 1 and (k + zeros - 1) != 0)
				ans[i] = (ans[i - 1] + nCrModPFermat(k + zeros - 1, zeros - 1, MOD)) % MOD;
			else
				ans[i] = ans[i - 1];
		}
	}
	//logarr(ans, 0, n - 1);
	ll ans2 = (ans[n - 1] + 1) % MOD;
	cout << ans2 << "\n";
#ifndef ONLINE_JUDGE
	clock_t end = clock();
	cout << "\n\nExecuted In: " << double(end - begin) / CLOCKS_PER_SEC * 1000 << " ms";
#endif
	return 0;
}