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 long long ll;
typedef long double ld;
typedef complex<ld> point;
const int maxn = 300 + 5;
const int mod = 998244353; 

int a[maxn];
int dp[maxn][maxn][maxn], dp1[maxn][maxn][maxn], dp2[maxn][maxn][maxn];

int main(){
	ios_base::sync_with_stdio(false);
	string s;
	int K;
	cin >> s >> K;
	int n = 0;
	int cnt = 0;
	for (int i = 0; i < (int)s.size(); i++){
		if (s[i] == '0'){
			a[n++] = cnt;
			cnt = 0;
		}
		else
			cnt ++;
	}
	a[n++] = cnt;
	int sum = 0;
	for (int i = n; i >= 0; i--){
		for (int j = 0; j <= 300; j++){
			for (int k = 0; k <= 300; k++){
				if (k > sum or k < j)
					dp[i][j][k] = 0;
				else if (i == n)
					dp[i][j][k] = (j == 0 and k == 0);
				else{
					dp[i][j][k] = (0ll + dp[i][j][k] + dp1[i+1][j-1][j-k+300] - (j-a[i+1] > 0 ? dp1[i+1][j-a[i+1]-1][j-k+300] : 0) + mod) % mod;
					dp[i][j][k] = (0ll + dp[i][j][k] + dp2[i+1][300][k] - (j > 0 ? dp2[i+1][j-1][k] : 0) + mod) % mod;
					dp[i][j][k] = (0ll + dp[i][j][k] + mod) % mod;
				}

				if (j){
					dp1[i][j][j-k+300] = (dp1[i][j-1][j-k+300] + dp[i][j][k]) % mod;
					dp2[i][j][k] = (dp2[i][j-1][k] + dp[i][j][k]) % mod;
				}
				else{
					dp1[i][j][j-k+300] = dp[i][j][k];
					dp2[i][j][k] = dp[i][j][k];
				}
			}
		}
		sum += a[i];
	}
	int answer = 0;
	for (int j = 0; j <= 300; j++)
		for (int k = 0; k <= min(300, K); k++)
			answer = (answer + dp[0][j][k]) % mod;
	cout << answer << endl;
}