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

Solution:
S, K = input().split()
K = int(K)
MOD = 998244353

L = []
o = "0"
z = "1"

if S[0] == o:
  L.append(0)
  cnt = 0
else:
  cnt = 1

for i in range(1, len(S)):
  if S[i] == o:
    L.append(cnt)
    cnt = 0
  else:
    cnt += 1
if cnt != 0:
  L.append(cnt)

N = len(L) 
s = sum(L)
M = min(s, K) + 1
DP = [[[0] * M for _ in range(M)] for _ in range(N)]

s -= L[0]
for i in range(min(s, K) + 1):
  DP[0][0][i] = 1

for i in range(1, N):
  s -= L[i]
  t = min(K, s) + 1
  for j in range(M):
    c = 0
    for k in range(M):
      c = (c + DP[i - 1][j][k]) % MOD
      if k - t >= 0:
        c -= DP[i - 1][j][k - t]
        if c < 0: c += MOD
      DP[i][j][k] = c
  t = min(K, L[i])
  for k in range(M):
    c = 0
    for j in range(k + 1):
      DP[i][j][k] = (DP[i][j][k] + c) % MOD
      c = (c + DP[i - 1][j][k]) % MOD
      if j - t >= 0:
        c -= DP[i - 1][j - t][k]
        if c < 0: c += MOD

ans = 0
for i in range(M):
  ans = (ans + DP[-1][i][i]) % MOD

print(ans)