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 int long long
using namespace std;
typedef pair<int,int> ii;

int mod = 998244353;

int pre[305][305]; ///total open, total close
int cur[305][305];
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	string S; cin >> S; int K; cin >> K;
	
	K = min(K, (int) S.length());
	reverse(S.begin(),S.end());
	
	vector<int> arr;
	
	int cnt = 0;
	for(char c : S){
		if(c == '0') arr.push_back(cnt), cnt = 0;
		else cnt++;
	}
	
	arr.push_back(0);
	int n = arr.size();
	
	
	
	pre[0][0] = 1;
	int total = 0;
	for(int i = 0;i < n;i++){
		total += arr[i];
		
		///open
		for(int c = 0;c <= total;c++){ 
			int acc = 0;
			for(int o = 0;o <= total;o++){
				acc += pre[o][c];
				acc %= mod;
				if(o > arr[i]) acc -= pre[o-arr[i]-1][c];
				acc %= mod;
				cur[o][c] += acc;
			}
		}
		
		///close
		for(int o = 0;o <= total;o++){
			int acc = 0;
			for(int c = 0;c <= o;c++){
				acc += pre[o][c];
				acc %= mod;
				cur[o][c] += acc;
			}
		}
		
		for(int o = 0;o <= total;o++){
			for(int c = 0;c <= total;c++){
				cur[o][c] -= pre[o][c];
			}
		}
		
		for(int o = 0;o <= total;o++){
			for(int c = 0;c <= total;c++){
				
				//cout << o << " " << c << " " << cur[o][c] << "\n";
				pre[o][c] = cur[o][c];
				pre[o][c] %= mod;
				if(pre[o][c] < 0) pre[o][c] += mod;
				cur[o][c] = 0;
			}
		}
		//cout << "\n\n";
	}
	
	//cout << K << "\n";
	int ans = 0;
	for(int i = 0;i <= K;i++){
		ans += pre[i][i];
		ans %= mod;
	}
	cout << ans;
}