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()
from random import randint
# k = 200
# s = "".join([str(randint(0,1)) for i in range(k)])
# print(s,k)

mod = 998244353
k = min(302, int(k))
n = len(s)
z = s.count("0")
S = [0] * (z+1)
ind = 0
for i in range(n):
    if s[i] == "0":
        ind += 1
    else:
        S[ind] += 1
# print(S)

D = [[0] * (k+1) for i in range(k+1)]
D[0][0] = 1
for ii in range(z+1):
    
    D0 = [[0] * (k+1) for i in range(k+1)]
    for j in range(k):
        if j+1 < k+1:
            for l in range(k+1):
                D0[j+1][l] = (D0[j+1][l] + D[j][l]) % mod
        if S[len(S)-1-ii] + j + 1 < k+1:
            # print("ind",S[len(S)-1-ii] + j + 1)
            for l in range(k+1):
                D0[S[len(S)-1-ii] + j + 1][l] = (D0[S[len(S)-1-ii] + j + 1][l] - D[j][l]) % mod

    for j in range(1, k+1):
        for l in range(k+1):
            D0[j][l] = (D0[j][l] + D0[j-1][l]) % mod

    D1 = [D[i][:] for i in range(k+1)]
    # D1[0][0] = 0
    for i in range(1, k+1):
        r = i-1
        c = 1
        while 0 <= r < k+1 and 0 <= c < k+1:
            # print("r c",r,c)
            D1[r][c] = (D1[r][c] + D1[r+1][c-1]) % mod
            r -= 1
            c += 1
    for i in range(1, k):
        r = k-1
        c = i+1
        while 0 <= r < k+1 and 0 <= c < k+1:
            D1[r][c] = (D1[r][c] + D1[r+1][c-1]) % mod
            r -= 1
            c += 1

    # for i in range(k):
    #     D1[i][0] = 0
    # for i in range(k):
    #     D1[k][i] = 0

    # print(D,D0,D1)
    for i in range(k+1):
        for j in range(k+1):
            D[i][j] = (D0[i][j] + D1[i][j]) % mod

# print(sum(D[i][i] for i in range(k+1)))
print(sum(D[0]) % mod)
# print(D)