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:
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=3e2+10, maxm=5e4+10, lg=21, mod=998244353, inf=1e18;

string s;
ll k,n,cnt,a[maxn],d[maxn],dp[maxn][maxn][maxn];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>s>>k;
	for(char c:s) (c=='0' ? cnt++:a[n++]=cnt);
	k=min(k,n);
	for(int i=0;i<n;i++) d[a[i]]++;
	dp[cnt+1][0][0]=1;
	for(int i=cnt+1;i;i--)for(int j=0;j<=k;j++)for(int k=0;k<=n;k++)if(dp[i][j][k])for(int t=0;t<=d[i-1]+k;t++) (dp[i-1][j+max(0ll,d[i-1]-t)][d[i-1]+k-t]+=dp[i][j][k])%=mod;
	ll ans=0;
	for(int i=0;i<=k;i++) ans+=dp[0][i][0];
	cout<<ans%mod;
	
	return 0;
}