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,b) for(int i=(a);i<=(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define PB push_back
#define ar2 array<int,2> 
#define vs vector<string>
typedef long long LL;
const int P = 998244353;
const int N = 305;
mt19937 rng(time(0));

int T, n, K, n0=0, n1;
char s[N];
int a[N], sum[N], dp[N][N][N], sdp[N][N][N];
//i-th, j-same, k-max

void madd(int &x, int y){
	x += y;
	x = (x>=P ? x-P : x);
}

int main() {
	cin>>(s+1)>>K;
	n = strlen(s+1);
	rep(i,1,n) if(s[i]=='0') n0++; else a[n0]++;
	sum[0] = a[0];
	rep(i,1,n0) sum[i] = sum[i-1] + a[i];
	n1 = n - n0;
	
	rep(i,0,n1) rep(j,0,i){
		dp[i][j][0] = sdp[i][j][0] = (min(i, a[0]) == j ? 1 : 0);
		//cout<<i<<" "<<j<<" 0 "<<dp[i][j][0]<<endl;
		rep(k,1,n0){
			if(sum[k]>i) {
				sdp[i][j][k] = sdp[i][j][k-1];
				continue;
			}
			rep(t,sum[k-1],i-1){
				if(j-min(i-t, a[k])<0) continue;
				madd(dp[i][j][k], sdp[t][j-min(i-t, a[k])][k-1]);
			}
			sdp[i][j][k] = sdp[i][j][k-1];
			madd(sdp[i][j][k], dp[i][j][k]);
			//cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
		}
	}
	
	int ans = 0;
	rep(j, max(0, n1-K), n1) madd(ans, sdp[n1][j][n0]);
	cout<<ans<<endl;
	return 0;
}