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 <stdio.h>
#include <string.h>
#define MOD 998244353

char x[310];
int next[310];
int p[5];
long long int check[310][310][310];
long long int func(int k, int s, int t)
{
	if(k==0) return 1;
	else if(k<0) return 0;
	if(check[k][s][t]!=-1) return check[k][s][t];
	
	//s>0 : 1, s<0 : 0
	long long int s1 = 0, s2 = 0;
	if(x[k]=='0')
	{
		s1 = func(k-1,s,t);
		if(s>=1) s2 = func(k,s-1,t);
	}
	else
	{
		if(t>= (k-next[k])) s1 = func(next[k]-1,s + (k-next[k]), t - (k-next[k]));
		s2 = func(k-1,s,t);
	}
	return check[k][s][t] = (s1+s2)%MOD;
}

int main()
{
	int a,b;
	scanf("%s %d",x+1,&b);
	a = strlen(x+1);
	if(b>=300) b = 300;
	for(int i=0;i<=a;i++) for(int j=0;j<=b;j++) for(int k=0;k<=b;k++) check[i][j][k] = -1;
	
	for(int i=1;i<=a;i++)
	{
		int k = x[i]-'0';
		next[i] = p[1-k];
		p[k] = i;
	}
	
	printf("%lld",func(a,0,b));
	//n k 
}