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;
typedef long long LL;

LL f[N][N][N], mod = 998244353, ans;
int n, m, last, cnt, a[N], sum[N];
char s[N];

int main() {
	cin>>(s + 1)>>m;
	n = strlen(s + 1);
	m = min(m, n);
	for(int i = 1; i <= n; i++) 
		if(s[i] == '0') a[++cnt] = i - last - 1, last = i;
	if(last != n)
		a[++cnt] = n - last;
	for(int i = cnt; i; i--)
		sum[i] = sum[i + 1] + a[i];
	f[cnt + 1][0][0] = 1;
	for(int i = cnt; i; i--)
		for(int j = 0; j <= m && j <= sum[i]; j++)
			for(int k = 0; k <= j; k++) {
				f[i][j][k] = f[i + 1][j][k];
				for(int p = 1; p <= a[i] && p <= j; p++)
					f[i][j][k] = (f[i][j][k] + f[i + 1][j - p][k - p])%mod;
				for(int p = 1; p <= j - k; p++)
					f[i][j][k] = (f[i][j][k] + f[i + 1][j][k + p])%mod;
			}
	for(int i = 0; i <= m; i++)
		ans = (ans + f[1][i][0])%mod;
	cout<<ans<<endl;
	return 0;
}