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 <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const long long mod = 998244353;
string S;
int K, no = 0;
vector<int> cnt;
vector<int> pfx;
long long dptable[301][301][301][2];
long long dp(int a, int b, int c, bool d) {
	if (b > no || c < 0) return 0;
	if (a == cnt.size()) return 1;
	if (dptable[a][b][c][d] != -1) return dptable[a][b][c][d];
	if (d == true) {
		if (a + 1 == cnt.size()) return dptable[a][b][c][d] = dp(a + 1, b, c, d);
		dptable[a][b][c][d] = 0;
		for (int i = max(b, pfx[a + 1]); i < b + cnt[a + 1]; ++i) dptable[a][b][c][d] += dp(a + 1, i, c, 1), dptable[a][b][c][d] %= mod;
		dptable[a][b][c][d] = (dptable[a][b][c][d] + dp(a + 1, b + cnt[a + 1], c, 0)) % mod;
		return dptable[a][b][c][d];
	} else return dptable[a][b][c][d] = (dp(a, b, c, 1) + dp(a, b + 1, c - 1, 0)) % mod;
}
int main() {
	memset(dptable, -1, sizeof dptable);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> S >> K;
	int x = 0;
	for (char c: S) {
		if (c == '1') ++x, ++no;
		else cnt.push_back(x), x = 0;
	}
	K = min(K, no);
	if (cnt.size() == 0) {
		cout << 1;
		return 0;
	}
	pfx.push_back(cnt[0]);
	for (int i = 1; i < cnt.size(); ++i) pfx.push_back(cnt[i] + pfx[i - 1]);
	cout << dp(0, cnt[0], K, false);
	return 0;
}