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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static final long MOD = 998244353;
	static int[] zeroes;
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		char[] vals = sc.next().toCharArray();
		int K = sc.nextInt();
		int tot = 0, z = 0;
		zeroes = new int[vals.length];
		for (int i = 0; i < vals.length; i++) {
			if (vals[i] == '1') {
				zeroes[tot++] = z;
			} else {
				z++;
			}
		}
		zeroes = Arrays.copyOf(zeroes, tot);
		if (K > zeroes.length) {
			K = zeroes.length;
		}
		int[] got = new int[z + 1];
		for (int zero : zeroes) {
			got[zero]++;
		}
		long[][][] table = new long[tot + 1][z + 2][K + 1];
		for (int i = 0; i <= z + 1; i++) {
			for (int j = 0; j <= K ; j++) {
				table[tot][i][j] = 1;
			}
		}
		for (int pos = tot - 1; pos >= 0; pos--) {
			for (int from = z; from >= 0 ; from--) {
				for (int rem = K; rem >= 0; rem--) {
					table[pos][from][rem] = table[pos][from + 1][rem];
					if (from <= zeroes[pos]) {
						for (int cant = 1; pos + cant <= tot && cant - got[from] <= rem; cant++) {
							int nRem = rem - Math.max(cant - got[from], 0);
							if (nRem >= 0) {
								table[pos][from][rem] += table[pos + cant][from + 1][nRem];
							}
						}
						table[pos][from][rem] %= MOD;
					}
				}
			}
		}
		
		out.println(table[0][0][K]);
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}