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 = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : v)
#define sz(v) int(v.size())
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const ll md = 998244353;

ll mem[301][301][301] = {};

int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);

	string s;
	int k;
	cin >> s >> k;
	s.push_back('0');
	k = min(k, 300);

	vi ls;
	for(int i = 0, cnt = 0; i < sz(s); ++i){
		if(s[i] == '0'){
			ls.push_back(cnt);
			cnt = 0;
		} else ++cnt;
	}
	while(!ls.empty() && ls.back() == 0) ls.pop_back();

	mem[0][0][k] = 1;

	rep(i,0,sz(ls)){
		rep(t,0,301) rep(c,0,k+1){
			ll cur = mem[i][t][c];
			cur %= md;
			mem[i+1][t][c] += cur; // neutral
			rep(x,1,c+1) if(t+x <= 300) mem[i+1][t + x][c - x] += cur; // get stuff
			rep(x,1,1+min(ls[i], t)) mem[i+1][t-x][c] += cur; // give stuff
		}
	}

	ll ans = 0;
	rep(c,0,k+1) ans += mem[sz(ls)][0][c];
	ans %= md;
	if(ans < 0) ans += md;
	cout << ans << endl;
}