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<cstdio>
#include<cstring>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=305,mod=998244353;
char s[N]; int n,m,t,lim,a[N],f[N<<1][N][N<<1],ans; //f[x][y][z]: x turns; position y; delta z
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	RI i,j,k,p; for (scanf("%s%d",s+1,&t),n=strlen(s+1),m=i=1;i<=n;++i)
	if (s[i]=='0') ++m; else ++a[m]; if (!a[m]) --m;
	f[0][0][0]=1; lim=(min(t,n)<<1);
	for (j=0;j<m;++j) for (i=0;i<=lim;++i) for (k=0;k<=n;++k) if (f[i][j][k])
	{
		inc(f[i][j+1][k],f[i][j][k]); //do nothing
		for (p=1;i+p<=lim;++p) inc(f[i+p][j+1][k+p],f[i][j][k]); //addition
		for (p=1;p<=min(k,a[j+1])&&i+p<=lim;++p) inc(f[i+p][j+1][k-p],f[i][j][k]); //subtraction
	}
	for (i=0;i<=(min(t,n)<<1);++i) inc(ans,f[i][m][0]);
	return printf("%d",ans),0;
}