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 mod 998244353
#define int long long
using namespace std;
const int N=310;
int n,K,dp[N][N][N],last,cnt;
int a[N],w,sum[N];
char s[N];
inline int min(int a,int b){return((a<b)?a:b);}
inline int max(int a,int b){return((a>b)?a:b);}
signed main()
{
	scanf("%s%lld",s+1,&K);
	n=strlen(s+1);
	for (int i=1;i<=n;i++) cnt+=(s[i]=='1');
	K=min(K,cnt);
	for (int i=1;i<=n;)
	{
		int j=i;
		if (s[i]=='0')
		{
			a[++w]=last;j++;last=-1;
			while (j<=n && s[i]==s[j]) w++,j++;
			i=j;
			continue;
		}
		while (j<=n && s[i]==s[j]) j++;
		last=j-i;
		i=j;
	}
	if (last!=-1) a[++w]=last;
	for (int i=1;i<=w;i++) sum[i]=sum[i-1]+a[i];
	dp[0][0][0]=1;
	for (int i=0;i<n;i++)
	{
		for (int j=sum[i];j<=cnt;j++)
		{
			for (int k=0;k<=K;k++)
			{
				if (!dp[i][j][k]) continue;
				for (int p=max(0,sum[i+1]-j);p<=cnt-j;p++)
				{
					int num=(a[i+1]>=p)?0:p-a[i+1];
					if (k+num>K) break;
					if (i+1==n && p>a[i+1]) break;
					dp[i+1][j+p][k+num]=(dp[i+1][j+p][k+num]+dp[i][j][k])%mod;
				}
			}
		}
	}
	int ans=0;
	for (int i=0;i<=K;i++) ans=(ans+dp[n][cnt][i])%mod;
	printf("%lld\n",ans);
}