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>
using namespace std;

typedef long long LL;

const int N=300,mod=998244353;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n,m,c[N+9],cc,cnt[N+9];
int dp[N+9][N+9][N+9],sum[N+9][N+9][2];

void work(){
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  int now=0;
  for (int i=1;i<=n;++i)
	s[i]=='0'?++now:c[++cc]=now;
  m=min(m,cc);
  for (int i=1;i<=cc;++i) ++cnt[c[i]];
  dp[now+1][0][0]=1;
  int count=0;
  for (int i=now;i>=0;--i){
	count+=cnt[i];
	//memset(sum,0,sizeof(sum));
    for (int j=0;j<=count;++j)
	  for (int k=0;k<=j&&k<=m;++k){
		sum[j][k][0]=dp[i+1][j][k];
		if (j&&k) sadd(sum[j][k][0],sum[j-1][k-1][0]);
		sum[j][k][1]=dp[i+1][j][k];
		if (j) sadd(sum[j][k][1],sum[j-1][k][1]);
	  }
	for (int j=0;j<=count;++j)
	  for (int k=0;k<=j&&k<=m;++k){
		if (j>cnt[i]&&k) sadd(dp[i][j][k],sum[j-cnt[i]-1][k-1][0]);
		sadd(dp[i][j][k],sum[j][k][1]);
		if (j>cnt[i]) ssub(dp[i][j][k],sum[j-cnt[i]-1][k][1]);
		//printf("%d %d %d : %d\n",i,j,k,dp[i][j][k]);
	  }
  }
  //printf("%d %d\n",count,cc);
  int ans=0;
  for (int k=0;k<=m;++k) sadd(ans,dp[0][count][k]);
  printf("%d\n",ans);
}

int main(){
  int T=1;
  //scanf("%d",&T);
  for (;T--;) work();
  return 0;
}