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;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=998244353;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=310;
char s[N];
int m,ss[N],p[N];
int dp[N][N][N],ans;

void upd(int &a,int b) {
	a+=b; if (a>=mod) a-=mod;
}
int main() {
	scanf("%s%d",s,&m);
	int n=strlen(s);
	reverse(s,s+n);
	m=min(m,n);
	int p0=0;
	rep(i,0,n) {
		if (s[i]=='0') ss[p0+1]=ss[p0],p0++;
		else p[p0]++,ss[p0]++;
	}

	dp[0][0][0]=1;
	rep(i,1,p0+2) rep(k,0,m+1) {
		int t=0;
		rep(j,0,ss[i-1]+1) {
			for (int z=0;z<p[i-1]&&z<=j;z++)
				upd(dp[i][j][k+p[i-1]-z],dp[i-1][j-z][k]);
			if (j-p[i-1]>=0) upd(t,dp[i-1][j-p[i-1]][k]);
			upd(dp[i][j][k],t);
		}
	}
	rep(i,0,m+1) upd(ans,dp[p0+1][ss[p0]][i]);
	printf("%d\n",ans);
}