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;

constexpr long long MOD = 998244353;

int main() {
	string S;
	long long K;
	cin >> S >> K;
	vector<int> V = { 0 };
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '0') V.push_back(0);
		else V[V.size() - 1]++;
	}
	int A = V.size(), B = S.size() - A + 1, N = S.size();
	vector<vector<vector<long long> > > DP(A + 1, vector<vector<long long> >(B + 1, vector<long long>(B + 1, 0)));
	DP[0][0][0] = 1;
	for (int i = 0; i < A; i++) {
		for (int j = 0; j <= B; j++) {
			long long NOW = 0;
			for (int k = 0; k <= B - j; k++) {
				NOW += DP[i][j + k][k];
				NOW %= MOD;
				DP[i + 1][j + k][k] = NOW;
			}
			NOW = 0;
			for (int k = 0; k <= B - j; k++) {
				NOW += DP[i][k][j + k];
				NOW %= MOD;
				DP[i + 1][k][j + k];
			}
		}
		for (int j = 0; j <= B; j++) {
			vector<long long> Cur(B + 2, 0);
			for (int k = B; k >= 0; k--) {
				Cur[k] = (Cur[k + 1] + DP[i][j][k]) % MOD;
				DP[i + 1][j][k] += (Cur[k + 1] - (Cur[min(B + 1, k + 1 + V[i])] % MOD) + MOD) % MOD;
				DP[i + 1][j][k] %= MOD;
			}
		}
		/*
		for (int j = 0; j <= B; j++) {
			for (int k = 0; k <= B; k++) {
				cout << DP[i + 1][j][k] << " ";
			}
			cout << endl;
		}
		cout << endl;
		*/
	}
	long long ANS = 0;
	for (int i = 0; i <= K && i <= B; i++) {
		ANS += DP[A][i][0];
		ANS %= MOD;
	}
	cout << ANS << endl;
}