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 llong long long
#define mkpr make_pair
#define x first
#define y second
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_
#define tm dolor_sit_amet_
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 300;
const int P = 998244353;
char s[mxN+3]; int a[mxN+3];
llong f[mxN+3][mxN+3][mxN+3],g1[mxN+3][mxN+3][mxN+3],g2[mxN+3][mxN+3][mxN+3];
int n,m,lim;

void updsum(llong &x,llong y) {x+=y-P,x+=(x>>31)&P;}

int main()
{
	scanf("%s",s+1); lim = read(); n = strlen(s+1); m = 0;
	for(int i=1; i<=n; i++)
	{
		if(s[i]=='1') {a[m+1]++;}
		else {m++;}
	}
	lim = min(lim,n-m);
	f[0][0][0] = 1ll;
	int s = 0;
	for(int i=1; i<=m; i++)
	{
		for(int j=0; j<=lim; j++)
		{
			for(int k=0; k<=n-m-s; k++) if(f[i-1][j][k])
			{
				updsum(g1[i][j][max(0,k-a[i])],f[i-1][j][k]);
				updsum(g1[i][j][k],P-f[i-1][j][k]);
				updsum(g2[i][j][k],f[i-1][j][k]);
			}
		}
		s += a[i];
		for(int j=0; j<=lim; j++)
		{
			for(int k=0; k<=n-m-s; k++)
			{
				if(k) {updsum(g1[i][j][k],g1[i][j][k-1]);}
				if(j&&k) {updsum(g2[i][j][k],g2[i][j-1][k-1]);}
				f[i][j][k] = (g1[i][j][k]+g2[i][j][k])%P;
			}
		}
	}
	llong ans = 0ll;
	for(int j=0; j<=lim; j++) for(int k=0; k<=a[m+1]; k++) {updsum(ans,f[m][j][k]);}
	printf("%lld\n",ans);
	return 0;
}