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;
long long dp[405][405][405];
long long MOD=998244353;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s;
	int K;
	cin>>s>>K;
	vector<int>v;
	int cnt=0, ones=0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='0'){
			v.push_back(cnt);
			cnt=0;
		}
		else{
			cnt++;
			ones++;
		}
		if(i+1==s.size()) v.push_back(cnt);
	}
	//for(int i:v) cout<<i<<endl;
	int n=v.size(), MAXN=ones;
	memset(dp, 0, sizeof dp);
	for(int i=0;i<n;i++){
		for(int j=0;j<=MAXN;j++){
			for(int k=0;k<=MAXN;k++){
				if(j<k) continue;
				if(i==0){
					if(j==k) dp[i][j][k]=1;
					continue;
				}
				for(int a=0;a<=v[i];a++){
					if(k+a>MAXN) break;
					dp[i][j][k]+=dp[i-1][j][k+a];
					//if(i==1 && j==1 && k==0) cout<<i-1<<" "<<j<<" "<<k+a<<endl;
				}
				for(int a=1;a<=k;a++){
					if(j-a<0 || k-a>MAXN) break;
					dp[i][j][k]+=dp[i-1][j-a][k-a];
					//if(i==1 && j==1 && k==0) cout<<i-1<<" "<<j-a<<" "<<k-a<<endl;
				}
				dp[i][j][k]%=MOD;
				//cout<<i<<" "<<j<<" "<<k<<": "<<dp[i][j][k]<<endl;
			}
		}
	}
	long long ans=0;
	for(int i=0;i<=min(K, MAXN);i++){
		ans=(ans+dp[n-1][i][0])%MOD;
	}
	cout<<ans;
}