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;
const int N=305,p=998244353;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
int n,m,K,ans,a[N],f[N][N],g[N][N];
char ch[N];
void check(int &x,int y){if ((x+=y)>=p) x-=p;}
void dp(int L){
	n+=L;
	for (int i=0;i<=n;i++)
	for (int j=i-1;j>=0;j--){
		g[i][j]=f[i][j+1];
		check(g[i][j],g[i][j+1]);
	}
	for (int i=1;i<=n;i++)
	for (int j=1;j<=i;j++) check(f[i][j],f[i-1][j-1]);
	for (int i=n;i;i--)
	for (int j=L+1;j<=i;j++)
	check(f[i][j],p-f[i-L-1][j-L-1]);
	for (int i=0;i<=n;i++)
	for (int j=0;j<=i;j++) check(f[i][j],g[i][j]);
}
int main(){
	scanf("%s %d",ch+1,&K);
	n=strlen(ch+1);
	int cnt=0;
	for (int i=1;i<=n;i++)
	if (ch[i]=='0'){a[++m]=cnt;cnt=0;}
	else cnt++;
	a[++m]=cnt;
	f[0][0]=1;n=0;
	for (int i=m;i;i--)
	dp(a[i]);
	for (int i=0;i<=min(n,K);i++) check(ans,f[i][0]);
	printf("%d\n",ans);
	return 0;
}