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;

const int maxn = 310;
const int mod = 998244353;

char str[maxn];
int a[maxn], s[maxn], m, len, K, ans;
int f[maxn][maxn<<1], g[maxn][maxn<<1], h[maxn][maxn<<1];

int mo(int x) {
	return x >= mod ? (x - mod) : x;
}

int main() {
	scanf("%s", str+1); scanf("%d", &K);
	len = int (strlen (str+1));
	str[len + 1] = '0';
	int c = 0;
	for (int i = 1; i <= len+1; i++) {
		if (str[i] == '0') {
			a[++ m] = c;
			c = 0;
		} else ++ c;
	}
	for (int i = 1; i <= m; i++) s[i] = s[i-1] + a[i];
	f[0][0] = 1;
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= s[m]; j++) {
			for (int k = 0; k <= s[m]; k++) {
				if (j) g[j][k] = mo(g[j-1][k] + f[j][k]);
				else g[j][k] = f[j][k];
				if (j && k) {
					h[j][k] = mo(h[j-1][k-1] + f[j][k]);
				} else {
					h[j][k] = f[j][k];
				}
			}
		}
		for (int j = 0; j < s[i]; j++) {
			for (int k = 0; k <= s[m]; k++) {
				f[j][k] = 0;
			}
		}
		for (int j = s[i]; j <= s[m]; j++) {
			for (int k = 0; k <= s[m]; k++) {
				f[j][k] = g[j][k];
				if (j >= a[i]) {
					f[j][k] = mo(f[j][k] + h[j-a[i]][k]);
					f[j][k] = mo(f[j][k] + mod - g[j-a[i]][k]);
				}
			}
		}
	}
	for (int i = 0; i <= min(K, s[m]); i++) ans = mo(ans + f[s[m]][i]);
	printf("%d\n", ans);
	return 0;
}