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 <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using ll = long long int;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = 998244353ll;

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll dp[310][310][310][2];
std::string s;

int main(void){
	int n,m,i,j,k,l;
	ll ans=0ll;
	std::cin >> s;
	std::cin >> l;
	n = s.l_ength();
	l = std::min(l,n);
	std::reverse(s.begin(),s.end());
	dp[0][0][0][0] = 1ll;
	for(i=0; i<n; ++i){
		if(s[i]=='0'){
			for(j=0; j<=l; ++j){
				for(k=0; k<=j; ++k){
					add_mod(dp[i+1][j][k][0],dp[i][j][k][0]);
					if(k){
						add_mod(dp[i+1][j][k][0],dp[i+1][j][k-1][0]);
					}
				}
			}
			for(j=0; j<=l; ++j){
				for(k=0; k<=j; ++k){
					add_mod(dp[i+1][j][k][0],dp[i][j][k][1]);
				}
			}
		}else{
			for(j=0; j<=l; ++j){
				for(k=0; k<=j; ++k){
					add_mod(dp[i+1][j][k][0],dp[i][j][k][0]);
					if(j+1<=l){
						add_mod(dp[i+1][j+1][k][1],dp[i][j][k][0]);
						add_mod(dp[i+1][j+1][k][1],dp[i][j][k][1]);
					}
				}
			}
		}
		/*
		for(j=0; j<=l; ++j){
			for(k=0; k<=j; ++k){
				printf("%d %d %d: %lld, %lld,;\n",i,j,k,dp[i+1][j][k][0],dp[i+1][j][k][1]);
			}
		}
		printf("\n");
		*/
	}
	for(j=0; j<=l; ++j){
		for(k=0; k<=j; ++k){
			add_mod(ans,dp[n][j][k][0]);
		}
	}
	std::cout << ans << std::endl;
	return 0;
}