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 cs const
#define pb push_back
using namespace std;
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
void Add(int &a, int b){ a = add(a,b); }
cs int N = 305;
int n, K; char S[N];
int a[N], len, dp[2][N][N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%s%d",S+1,&K); 
	K=min(K,n=strlen(S+1));S[n+1]='0';
	for(int i=1,pt=0; i<=n+1; i++){
		if(S[i]=='1')continue;
		a[++len]=i-pt-1; pt=i;
	} int now=0, nxt=1;
	dp[0][0][0]=1;
//	for(int i=1; i<=len; i++)
//	cout << a[i] << " "; cout << endl;
	for(int i=1; i<=len; i++){
		memset(dp[nxt],0,sizeof(dp[nxt]));
		for(int k=0; k<=K; k++){
			static int sm[N]; sm[0]=0;
			for(int l=1; l<=K; l++)
			sm[l]=add(sm[l-1],dp[now][l][k]);
			for(int j=0; j<=K; j++)
			Add(dp[nxt][j][k],dec(sm[min(K,j+a[i])],sm[j])); 
		} static int sm[N][N];
		for(int j=0; j<=K; j++)
		for(int k=0; k<=K; k++){
			sm[j][k] = dp[now][j][k];
			if(j && k) Add(sm[j][k],sm[j-1][k-1]);
			Add(dp[nxt][j][k],sm[j][k]);
		} swap(now, nxt);
	} 
	int ans = 0;
	for(int j=0; j<=K; j++)
	Add(ans, dp[now][0][j]);
	cout << ans; return 0;
}