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>
#define inc(l,i,r) for (int i=l;i<=r;i++)
#define dec(r,i,l) for (int i=r;i>=l;i--)
#define SIZE(V) ((int) V.size())
#define forE(p,u) for (edge *p=head[u];p;p=p->nxt)
#define forV(i,V) for (int i=0;i<SIZE(V);i++)
#define pb push_back
#define In inline
#define fi first
#define se second
#define mp make_pair
#define It iterator
#define ___ putchar(10);
#define cnt(x) __builtin_popcount(x)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N = 100100, P = 998244353;

char S[1010];
int n, m, k, a[310], dp1[310][310], dp2[310][310], ans;

int main() {
	scanf("%s%d",S+1,&k);

	{
		int len = strlen(S+1), cnt = 0;
		inc(1,i,len) {
			if (S[i] == '0') a[++n] = cnt, cnt = 0;
			else ++cnt;
		}
		if (cnt) a[++n] = cnt, cnt = 0;
	}
	inc(1,i,n) m += a[i];
	// inc(1,i,n) printf("%d ",a[i]);  puts("");

	//dp[tot][now]
	dp1[0][0] = 1;
	dec(n,i,1) {
		inc(0,x,m) dec(x,y,0) dp2[x][y] = (dp1[x][y] + dp2[x][y+1]) % P;
		inc(1,j,a[i]) {
			inc(0,x,m) inc(0,y,x) if (x-j >= 0 && y-j >= 0) dp2[x][y] = (dp2[x][y] + dp1[x-j][y-j]) % P;
		}

		inc(0,x,m) inc(0,y,x) dp1[x][y] = dp2[x][y], dp2[x][y] = 0;
		// printf("i=%d\n",i);
		// inc(0,x,m) {
		// 	inc(0,y,m) printf("%d ",dp1[x][y]);
		// 	puts("");
		// }
	}

	inc(0,x,min(m,k)) ans = (ans + dp1[x][0]) % P;
	printf("%d\n",ans);
}