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 ll long long
#define mo 998244353
#define N 410
using namespace std;
string s;
ll dp[N][N][N],ans,d[N][N][2];
int k,n,ma,a[N],na,m;
void add(ll &x,ll y){x=(x+y)%mo;}
int main(){
	cin>>s>>k;n=s.length();k=min(k,n);
	for (int i=1,la=0;i<=n;i++){if (s[i-1]=='0'){a[++na]=i-la-1;la=i;}if (i==n)a[++na]=i-la;}
	n=na;for (int i=1;i<=na;i++)m+=a[i];
	dp[0][0][0]=1;
	for (int i=0,s=0;i<na;i++,s+=a[i]){
		for (int j=s;j<=m;j++){
			for (int l=0;l<=k;l++){
				add(d[j][l][0],dp[i][j][l]);
				if (j+a[i+1]<=m){
					add(d[min(m+1,j+a[i+1])][l][0],mo-dp[i][j][l]);
					add(d[j+a[i+1]][l][1],dp[i][j][l]);
				}
			}
		}
		for (int j=0;j<=m;j++){
			for (int l=0;l<=k;l++){
				add(d[j+1][l][0],d[j][l][0]),add(d[j+1][l+1][1],d[j][l][1]);
				add(dp[i+1][j][l],d[j][l][0]+d[j][l][1]);d[j][l][0]=d[j][l][1]=0;
			}
		}
	}
	for (int i=0;i<=k;i++)add(ans,dp[n][m][i]);
	cout<<ans<<endl;
	return 0;
}