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
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    s,K=input().split()
    K=int(K)
    
    l=len(s)
    if K>l:
        K=l
    sep=[]
    count=0
    for i in range(l):
        if s[i]=="1": count+=1
        else:
            sep.append(count)
            count=0

    sep.append(count)

    dp=[[[0]*(l+1) for _ in range(K+1)] for _ in range(len(sep))]
    #dp[i][j][k] 末尾からi番目の領域、j個の0をストック,k回の操作
    dp[0][0][0]=1
    for i in range(1,min(sep[-1]+1,K+1)):
        dp[0][i][i]=1
    dp20=[[0]*(l+1) for _ in range(K+1)]
    for i in range(1,len(sep)):
        ori=sep[-1-i]
        dp2=deepcopy(dp20)
        for k in range(K+1):
            dp[i][k][-1]=dp[i-1][k][-1]
            for j in range(1,l+1):
                dp[i][k][-1-j]=(dp[i][k][-j]+dp[i-1][k][-1-j])%mod
                if k==0 or j==0: continue
                
                dp2[k][j]=(dp2[k-1][j-1]+dp[i-1][k-1][j-1])%mod
                if j>ori and k>ori:
                    dp2[k][j]-=dp[i-1][k-ori-1][j-ori-1]
                    dp2[k][j]%=mod
        for k in range(K+1):
            for j in range(1,l+1):
                dp[i][k][j]=(dp[i][k][j]+dp2[k][j])%mod
    

    ans=0
    for k in range(K+1):
        ans+=dp[-1][k][0]
        ans%=mod
    print(ans)
    #print(dp)




if __name__ == "__main__":
    main()