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:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

#a,b,c,d = map(int,readline().split())
s,k = readline().split()


a = [len(i) for i in s.split("0")]
while a and a[-1] == 0: a.pop()

if not a:
    print(1)
    exit()

MOD = 998244353

M = sum(a)+1
k = min(int(k),M)


dp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
dp[0][0] = 1

#print(a)
for ai in a[::-1]:
    ndp = [[0]*M for _ in range(k+1)] # j 使って（上限 k）、l 余ってる
    for j in range(k+1):
        for l in range(M):
            if dp[j][l]:
                for ll in range(l):
                    ndp[j][ll] += dp[j][l]
                    ndp[j][ll] %= MOD

                V = min(M-l,k-j+1,ai+1)
                for i in range(V):
                    #if j+i > k: break
                    ndp[j+i][l+i] += dp[j][l]
                    ndp[j+i][l+i] %= MOD
    
    dp = ndp
    #print(dp)

ans = 0
for jj in range(k+1):
    ans += dp[jj][0]

print(ans%MOD)