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;
using UL = unsigned int;
using ULL = unsigned long long;
using LL = long long;
#define rep(i, n) for(UL i = 0; i < (n); i++)

const ULL M = 998244353;

ULL dp[302][302][302][2] = {};
UL K;
UL N = 0;
vector<UL> P;

ULL Solve() {
	UL I = P.size() - 2;
	UL mK = min(K, I);
	dp[0][0][0][0] = 1;
	for (UL i = 0; i <= I; i++) {
		for (UL k = 0; k <= mK; k++) {
			for (UL n = N; n != (UL)-1; n--) {
				if (i) if (n > 1) dp[i][k][n - 1][1] += dp[i][k][n][1];
			}
		}
		UL d = P[i + 1] - P[i];
		if (d) {
			for (UL k = 0; k <= mK; k++) {
				for (UL n = N; n != d - 1; n--)
					dp[i][k][n][0] = dp[i][k][n - d][0] + dp[i][k][n - d + 1][1];
				dp[i][k][d - 1][0] = dp[i][k][0][1];
				for (UL n = d - 2; n != (UL)-1; n--)
					dp[i][k][n][0] = 0;

				for (UL n = N; n != (UL)-1; n--) dp[i][k][n][1] = 0;
			}
		}
		for (UL k = 0; k <= mK; k++) {
			for (UL n = N; n != (UL)-1; n--) {
				dp[i][k][n][0] %= M;
				dp[i][k][n][1] %= M;
				if (k != mK) if(i != I) if(n != 0) dp[i + 1][k + 1][n][1] += dp[i][k][n][0] + dp[i][k][n][1];
				if (i != I) dp[i + 1][k][n][0] += dp[i][k][n][0];
			}
		}
	}
	ULL ans = 0;
	for (UL k = 0; k <= mK; k++) {
		for (UL n = 0; n <= N; n++) {
			ans += dp[I][k][n][0] + dp[I][k][n][1];
		}
	}
	ans %= M;
	return ans;
}

int main() {
	string S; cin >> S;
	cin >> K;
	P.push_back(0);
	for (char c : S) {
		if (c == '1') P.push_back(N);
		else N++;
	}
	P.push_back(N);
	N++;
	cout << Solve() << endl;
	return 0;
}