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<cstdio>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 3e2 + 5;
const int mod = 998244353;
int f[maxn][maxn][maxn], K, N, n, num[maxn], ans;
	//x     k     owe 
char s[maxn];
void Add(int &x, const int &a) {
	x = (x + a) >= mod ? x + a - mod : x + a;
}

int main() {
	scanf("%s%d", s, &K);
	N = strlen(s), n = 1;
	f[0][0][0] = 1;
	For(i, 0, N - 1) {
		if(s[i] == '0') ++n;
		if(s[i] == '1') ++num[n];
	}
	K = min(K, N);
	For(i, 0, n - 1) 
		For(j, 0, K)
			For(k, 0, j) {
				Add(f[i + 1][j][k], f[i][j][k]);
				// in
				For(l, 1, K - j)
					Add(f[i + 1][j + l][k + l], f[i][j][k]);
				// out
				For(l, 1, min(k, num[i + 1]))
					Add(f[i + 1][j][k - l], f[i][j][k]);
			}
	For(i, 0, K) Add(ans, f[n][i][0]);
	printf("%d", ans);
	return 0;
}