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>
#define ll long long
#define ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
#define all(v) v.begin(),v.end()
using namespace std;
const int mo=998244353;
const int N=305;
char s[N];
int n,k,a[N];
int f[N][N];
int s1[N][N];
int s2[N][N];
int main(){
	scanf("%s%d",s+1,&k);
	n=strlen(s+1);
	int p=1;
	For(i,1,n)
		if (s[i]=='0') p++;
		else a[p]++;
	f[0][0]=1;
	int sum=0,ss=0;
	For(i,1,p) ss+=a[i];
	For(i,1,p){
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		For(j,0,ss) For(k,0,ss){
			int p=min(ss+1,j+a[i]+1);
			if (p<=ss) s2[p][k+1]=(s2[p][k+1]+f[j][k])%mo;
			s1[j][k]=(s1[j][k]+f[j][k])%mo;
			s1[p][k]=(s1[p][k]+mo-f[j][k])%mo;
		}
		sum+=a[i];
		For(j,0,ss) For(k,0,ss){
			s1[j+1][k]=(s1[j+1][k]+s1[j][k])%mo;
			s2[j+1][k+1]=(s2[j+1][k+1]+s2[j][k])%mo;
			if (j>=sum) f[j][k]=(s1[j][k]+s2[j][k])%mo;
			else f[j][k]=0;
		}
		//cout<<f[sum][0]<<' '<<f[sum][1]<<endl;
	}
	int ans=0;
	For(i,0,min(k,ss)) ans=(ans+f[ss][i])%mo;//cout<<f[ss][i]<<endl;
	cout<<ans<<endl;
}