Problem: Given is a string S consisting of `0` and `1`. Find the number of strings, modulo 998244353, that can result from applying the following operation on S between 0 and K times (inclusive):

* Choose a pair of integers i, j (1\leq i < j\leq |S|) such that the i-th and j-th characters of S are `0` and `1`, respectively. Remove the j-th character from S and insert it to the immediate left of the i-th character.

Constraints

* 1 \leq |S| \leq 300
* 0 \leq K \leq 10^9
* S consists of `0` and `1`.

Input

Input is given from Standard Input in the following format:


S K


Output

Find the number of strings, modulo 998244353, that can result from applying the operation on S between 0 and K times (inclusive).

Examples

Input

0101 1


Output

4


Input

01100110 2


Output

14


Input

1101010010101101110111100011011111011000111101110101010010101010101 20


Output

113434815

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
void add(int &x,int y){
	x=(x+y)%mod;
}
int n,k,f[305][305][305],cnt[505],suf[505];
char s[505];
signed main(){
	scanf("%s%d",(s+1),&k);
	n=strlen(s+1);k=min(n,k);
	int res=0,tot=0;
	//cout<<n<<" "<<k<<endl;
	for(int i=1;i<=n;++i)
		if(s[i]=='0') cnt[++tot]=res,res=0;
		else ++res;
	if(res) cnt[++tot]=res;
	for(int i=tot;i>=1;--i)
		suf[i]=suf[i+1]+cnt[i];
	f[0][0][0]=1;
	for(int i=1;i<=tot;++i)
		for(int one=0;one<=n;++one)
			for(int st=0;st<=k;++st)
				if(f[i-1][one][st]){
					for(int v=0;v<=cnt[i];++v){
						int tmp=one-(cnt[i]-v);
						if(tmp>=0 && tmp<=suf[i+1]){
							//if(tmp>300) return puts("-1"),int(0);
							add(f[i][tmp][st],f[i-1][one][st]);
						} 
					}
					for(int v=cnt[i]+1;one-(cnt[i]-v)<=suf[i+1];++v){
						int tmp=one-(cnt[i]-v);
						if(tmp>=0 && tmp<=suf[i+1]){
							//if(tmp>300 || st+v-cnt[i]>300) return puts("-1"),int(0);
							add(f[i][tmp][st+v-cnt[i]],f[i-1][one][st]);	
						} 
					}
				}
	int ans=0;
	for(int st=0;st<=k;++st)
		add(ans,f[tot][0][st]);
	cout<<ans;
	return 0;	
}