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 N = 305;
const int MOD = 998244353;

int n, m, f[N][N][N], s[N], a[N];
char str[N];

int main()
{
	scanf("%s%d", str + 1, &m);
	n = strlen(str + 1);
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + (str[i] == '1');
	int tot = 0, ls = 0;
	for (int i = 1; i <= n; i++)
		if (str[i] == '0') a[++tot] = s[i] - s[ls], ls = i;
	a[++tot] = s[n] - s[ls];
	for (int i = 1; i <= tot; i++) s[i] = s[i - 1] + a[i];
	f[0][0][0] = 1;
	for (int i = 0; i < tot; i++)
		for (int j = s[i]; j <= s[tot]; j++)
			for (int k = 0; k <= j; k++) if (f[i][j][k])
				for (int l = max(0, s[i + 1] - j); l <= s[tot] - j; l++)
					if (l > a[i + 1]) (f[i + 1][j + l][k + l - a[i + 1]] += f[i][j][k]) %= MOD;
					else (f[i + 1][j + l][k] += f[i][j][k]) %= MOD;
	int ans = 0;
	for (int i = 0; i <= min(n, m); i++) (ans += f[tot][s[tot]][i]) %= MOD;
	printf("%d\n", ans);
	return 0;
}