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:
import sys
input = sys.stdin.readline

S,K=input().split()
K=int(K)
mod=998244353

LEN=len(S)

ONES=[]
Z=0
for s in S:
    if s=="0":
        Z+=1
    else:
        ONES.append(Z)

if ONES==[]:
    print(1)
    sys.exit()

O=len(ONES)
Z=ONES[-1]

DP=[[0]*(O+1) for i in range(min(O,K)+1)]
DP[0][0]=1

# DP[i][j]で, i個石を動かし、j個石が残っているときの場合の数

from collections import Counter
C=Counter(ONES)

for numb in range(Z,-1,-1):
    #print(DP)
    c=C[numb]

    NDP=[[0]*(O+1) for i in range(min(O,K)+1)]

    for i in range(min(O,K)+1):        
        for j in range(O+1):
            if DP[i][j]==0:
                continue
            for oku in range(c+j+1):
                if i+max(0,oku-c)<=min(O,K) and 0<=c+j-oku<=O:
                    NDP[i+max(0,oku-c)][c+j-oku]=(NDP[i+max(0,oku-c)][c+j-oku]+DP[i][j])%mod
    DP=NDP

ANS=0
for i in range(min(O,K)+1):
    ANS+=DP[i][0]

print(ANS%mod)