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 <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack> 
#include <bitset>
#include <queue>
#include <assert.h>
using namespace std;

const int N = 310;
const int mod = 998244353;
int dp[N][N][N];
char s[N];
vector<int> v;

/*
 * dp[i][j]
 *
 */

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

int main()
{
	int m;
	scanf("%s%d", s + 1, &m);
	int n = strlen(s + 1);
	int cnt = 0;
	s[0] = '0';
	for (int i = n; i >= 0; i--) {
		if (s[i] == '0') {
			v.push_back(cnt);
			cnt = 0;
		} else {
			cnt++;
		}
	}
	if (v.size() == 1) {
		cout << 1 << endl;
		return 0;
	}

	m = min(m, n);
	for (int j = 0; j <= v[0]; j++)
		dp[0][j][j] = 1;

	for (int i = 0; i + 1 < v.size(); i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= n; k++) {
				if (dp[i][j][k] == 0) continue;
				int valid = v[i + 1];
				for (int r = 1; r <= valid; r++)
					add(dp[i + 1][j + r][k + r], dp[i][j][k]);
				for (int r = 0; r <= k; r++)
					add(dp[i + 1][j][r], dp[i][j][k]);
			}
		}
	}

    int ans = 0;
	for (int i = 0; i <= m; i++)
		add(ans, dp[v.size() - 1][i][0]);

	cout << ans << endl;
	return 0;
}