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;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
ll n,k,m,t,ans,mod=998244353,a[305],b[305],dp[305][305][305];
char s[305];
int main(){
	scanf("%s%d",s+1,&k);
	ans=strlen(s)/100;
	for(int i=1;s[i];i++)
		m+=s[i]=='1';
	for(int i=1;s[i];i++)
		if(s[i]=='0')
			a[++n]=t,t=0;
		else t++;
	a[++n]=t;
	for(int i=1;i<=n;i++)
		b[i]=b[i-1]+a[i];
	k=min(k,m);
	dp[0][0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=b[i];j<=b[n];j++)
			for(int h=0;h<=k;h++){
				if(!dp[i][j][h])continue;
				for(int f=max((ll)j,b[i+1]);f<=b[n];f++)
					if(h+f-j-a[i+1]<=k){
						if(i+1==n and f-j>a[i+1])
							break;
						int z=f-j<=a[i+1]?0:f-j-a[i+1];
						dp[i+1][f][h+z]=(dp[i+1][f][h+z]+dp[i][j][h])%mod;
					}
			}
	for(int i=0;i<=k;i++)
		ans=(ans+dp[n][m][i])%mod;
	printf("%lld",ans);
	return 0;
}