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>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define forn(i,n) for(int i=0;i<n;i++)
#define minf numeric_limits<int>::min()
#define inf numeric_limits<int>::max()
#define linf numeric_limits<long>::max()
#define lminf numeric_limits<long>::min()
#define llinf numeric_limits<long long>::max()
#define llminf numeric_limits<long long>::min()
#define forln(i,n) for(long i=0;i<n;i++)
#define forlln(i,n) for(long long i=0;i<n;i++)
#define For(i,s,e) for(int i=s; i<=e; i++)
#define rFor(i,s,e) for(int i=s; i>=e; i--)
#define ll long long
#define l long
#define ivec vector<int>
#define lvec vector<l>
#define llvec vector<ll>
#define iimap map<int, int>
#define llmap map<ll, ll>
#define illmap map<int, ll>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ipair pair<int,int>
#define lpair pair<l,l>
#define llpair pair<ll,ll>
#define vec vector
#define CASE int t; cin>>t; while(t--)
#define len(a) a.size()
#define all(a) a.begin(), a.end()

using namespace std;
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
template<typename T> istream & operator>>(istream& in, vec<T> &a){
	forn(i,a.size()) in>>a[i];
	return in;
}   
template<typename T> ostream & operator<<(ostream& out, vec<T> &a){
	forn(i,a.size()) out<<a[i]<<" ";
	out<<endl;
	return out;
}  
template<typename T> T max(vec<T> a){
	T ans=numeric_limits<T>::min();
	forn(i, a.size()) ans=max(ans, a[i]);
	return ans;
}
template<typename T> T min(vec<T> a){
	T ans=numeric_limits<T>::max();
	forn(i, a.size()) ans=min(ans, a[i]);
	return ans;
}

ll mod=998244353;
ll modpow(ll u, ll p, ll mod){
    ll ret=1;
    while(p>0){
        if(p&1) ret=(ret*u)%mod;
        u=(u*u)%mod;
        p>>=1;
    }
    return ret;
}
llvec fac(1e5+10,1), ifac(1e5+10,1);
ll modinv(ll u){
	return modpow(u,mod-2,mod);
}
ll ncr(int n, int r){
	if(n<0 || r<0 || r>n) return 0;
	return ((fac[n]*ifac[r]%mod)*ifac[n-r]%mod);
}
void init(){
	fac[0]=1;
	For(i,1,len(fac)-1) fac[i]=(fac[i-1]*i)%mod, ifac[i]=modinv(fac[i]);
}

int main(){
	ios_base::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
		freopen("../input.txt","r",stdin);
		freopen("../output.txt","w",stdout);
	#endif
	init();
	int n, k;
	cin>>n>>k;
	string s;
	cin>>s; s+="1";
	int c=0;
	forn(i,n) c+=s[i]=='1'; 
	if(k==0 || c<k) return cout<<1<<endl,0;

	int st=0, en=0, ct=(s[0]=='1');
	ll ans=0;
	while(en!=n){
		while(en<n && ct<=k) ct+=(s[++en]=='1');
		// cout<<st<<" "<<en<<endl;
		if(en!=n){
			ans=(ans+ncr(en-st-1,k))%mod;
		}
		else{
			ans=(ans+ncr(en-st,k))%mod;
		}
		while(st<en && ct>k) ct-=(s[st++]=='1');
	}
	cout<<ans<<endl;
}