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;

typedef pair<int,int> pi;
typedef long long ll;

const ll mod = 998244353;

string s;
ll K, dp[305][305][305]; // groups, moves, carry
ll N, sz[305];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> s >> K;

	int gn = 1, gz = 0;
	N = s.size();
	K = min(K,N);
	reverse(s.begin(),s.end());

	for (int i = 0; i < s.size(); ++i){
		if (s[i] == '0'){
			sz[gn] = gz;
			gz = 0;
			gn++;
		}
		else gz++;
	}
	sz[gn] = gz;
	/*
	for (int i = 1; i <= gn; ++i){
		cout << sz[i] << ' ';
	}
	cout << '\n';
	*/
	dp[0][0][0] = 1;
	for (ll i = 1; i <= gn; ++i){
		for (ll k = 0; k <= K; ++k){
			for (ll c = 0; c <= k; ++c){
				for (ll l = 0; (c+l) <= k; ++l){
					dp[i][k][c] += dp[i-1][k][c+l];
					dp[i][k][c] %= mod;
				}
				for (ll l = 1; l <= min(min(sz[i],k),c); ++l){
					dp[i][k][c] += dp[i-1][k-l][c-l];
					dp[i][k][c] %= mod;
				}
				//cout << i << ' ' << k << ' ' << c << ' ' << dp[i][k][c] << '\n';
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= K; ++i){
		ans += dp[gn][i][0];
		ans %= mod;
	}
	cout << ans << '\n';
	
}