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:
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int N = 310;
const ll MOD = 998244353;

string s;
int k;
ll dp[N][N];
ll dp2[N][N];

void add(ll& a, ll b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> s >> k;
	reverse(ALL(s));
	int cnt = 0;
	vector<int> vv;
	int mx = 0;
	for (char c : s) {
		if (c == '1') {
			++cnt;
			++mx;
		} else {
			vv.push_back(cnt);
			cnt = 0;
		}
	}
	vv.push_back(cnt);
	k = min(k, mx);

	dp[0][0] = 1;

	int sm = 0;
	for (int i = 0; i < vv.size(); ++i) {
		memset(dp2, 0, sizeof(dp2));
		for (int cur = 0; cur <= sm; ++cur) {
			for (int used = cur; used <= sm && used <= k; ++used) {
				for (int now = 0; now <= cur; ++now) {
					add(dp2[cur - now][used], dp[cur][used]);
				}
				for (int now = 1; now <= vv[i] && used + now <= k; ++now) {
					add(dp2[cur + now][used + now], dp[cur][used]);
				}
			}
		}

		memcpy(dp, dp2, sizeof(dp));
		sm += vv[i];
	}

	ll ans = 0;
	for (int i = 0; i <= k; ++i) {
		add(ans, dp[0][i]);
	}
	cout << ans << "\n";
	return 0;
}