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 debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
template<class T> void rd(T &x) {
	x=0; int f=1,ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10-'0'+ch;ch=getchar();}
	x*=f;
}
template<class T> inline bool Cmin(T &x,T y) {return x>y?x=y,1:0;}
const int mod=998244353;
const int maxn=300+5;
int n,k; char S[maxn];
int a[maxn];
int dp[maxn][maxn][maxn];
inline void add(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
inline void sub(int &x,int y) {x-=y; if(x<0) x+=mod;}
void init() {
	int len=strlen(S);
	S[len]='0';
	for(int i=0,cnt=0;i<=len;++i) {
		if(S[i]=='0') a[++n]=cnt,cnt=0;
		else ++cnt;
	}
	int sum=0;
	for(int i=1;i<=n;++i) sum+=a[i];
	Cmin(k,sum);
}
int main() {
	scanf("%s",S);
	rd(k);
	init();
	dp[0][0][0]=1;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=k;++j) for(int h=j;h<=k;++h) {
			add(dp[i][j][h],dp[i-1][j][h]);
			if(j&&h) add(dp[i][j][h],dp[i][j-1][h-1]);
		}
		for(int h=0;h<=k;++h) {
			int sum=0;
			for(int j=h;j>=0;--j) {
				add(sum,dp[i-1][j+1][h]);
				if(j+a[i]<h) sub(sum,dp[i-1][j+a[i]+1][h]);
				add(dp[i][j][h],sum);
			}
		}
	}
	int an=0;
	for(int h=0;h<=k;++h) {
		add(an,dp[n][0][h]);
	}
	printf("%d\n",an);
	return 0;
}