AtCoder Grand Contest 046 - Shift

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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(s, k) = input().split()
mod = 998244353
k = int(k)
k = min(300, k)
raw = [0]
l = len(s)
for i in range(l):
	if s[i] == '0':
		raw.append(0)
	else:
		raw[-1] += 1
now = [[0 for _ in range(k + 1)] for _ in range(k + 1)]
l = len(raw)
raw.reverse()
now[0][0] = 1
for x in raw:
	last = now[:]
	now = []
	for i in range(k + 1):
		use = last[i][:]
		use.reverse()
		cum = []
		for j in range(k + 1):
			if cum:
				cum.append(cum[-1] + use[j])
				cum[-1] %= mod
			else:
				cum = [use[0]]
		cum.reverse()
		now.append(cum)
	cum2 = []
	for i in range(k + 1):
		cum = [0 for _ in range(i)]
		cum.append(last[i][0])
		for l in range(i + 1, k + 1):
			cum.append(cum[-1] + last[l][l - i])
		cum2.append(cum)
	for i in range(k + 1):
		for j in range(k + 1):
			if j > i:
				pass
			now[i][j] += cum2[i - j][i]
			if i - x - 1 >= 0:
				now[i][j] -= cum2[i - j][i - x - 1]
			now[i][j] %= mod
	for i in range(k + 1):
		for j in range(k + 1):
			now[i][j] -= last[i][j]
			now[i][j] %= mod
ans = 0
for i in range(k + 1):
	ans += now[i][0]
print(ans % mod)


(S, K) = input().split()
K = int(K)
K = min(K, 300)
mod = 998244353
a = []
val = 0
for i in range(len(S)):
	if S[i] == '0':
		a.append(val)
		val = 0
	else:
		val += 1
if val != 0:
	a.append(val)
m = len(a)
K = min(sum(a), K)
dp = [[0 for i in range(K + 1)] for j in range(K + 1)]
for j in range(K + 1):
	dp[j][j] = 1
b = [a[i] for i in range(m)]
c = [a[i] for i in range(m)]
for i in range(1, m):
	b[i] += b[i - 1]
b = [0] + b
for i in range(m - 2, -1, -1):
	c[i] += c[i + 1]
for i in range(m - 1, -1, -1):
	ndp = [[0 for j in range(K + 1)] for k in range(K + 1)]
	for k in range(min(b[i], K) + 1):
		for j in range(min(K, k + c[i]) + 1):
			M = max(k - j, -a[i])
			for l in range(max(0, M), K - j + 1):
				ndp[j][k] = (ndp[j][k] + dp[j + l][k]) % mod
			for l in range(1, min(K - k, -M) + 1):
				ndp[j][k] = (ndp[j][k] + dp[j][k + l]) % mod
	dp = ndp
print(dp[0][0])


def main():
	mod = 998244353
	(s, k) = input().split()
	(k, n, one, cnt, z, zero_list) = (int(k), len(s), s.count('1') + 1, 0, 0, [])
	for i in range(n):
		if s[i] == '0':
			zero_list.append(cnt)
			cnt = 0
		else:
			cnt += 1
	mm = min(one - 1, k)
	dp = [[0] * (mm + 1) for _ in [0] * one]
	dp[0][0] = 1
	for i in zero_list:
		dp2 = [[0] * (mm + 1) for _ in [0] * one]
		for j in range(one):
			for l in range(max(z + i - j, 0), one - j):
				ml = max(l - i, 0)
				for p in range(min(j, mm - ml) + 1):
					dp2[j + l][p + ml] = (dp2[j + l][p + ml] + dp[j][p]) % mod
		z += i
		dp = dp2
	print(sum([sum(i) for i in dp]) % mod)
main()


(S, K) = input().split()
S = list(S)
ori = [0]
for i in range(len(S) - 1, -1, -1):
	if S[i] == '0':
		ori.append(0)
	else:
		ori[-1] += 1
N = len(ori)
K = int(K)
K = min(310, K)
mod = 998244353
dp = [[[0] * (K + 1) for i in range(K + 1)] for j in range(N + 10)]
dp[-1][0][0] = 1
for i in range(N):
	for k in range(K + 1):
		for x in range(k + 1):
			dp[i][k][x] += dp[i - 1][k][x]
	for x in range(K + 1):
		nsum = 0
		for k in range(K + 1):
			if x <= k:
				dp[i][k][x] += nsum
				dp[i][k][x] %= mod
			nsum += dp[i - 1][k][x]
			if k - ori[i] >= 0:
				nsum -= dp[i - 1][k - ori[i]][x]
			nsum %= mod
	for k in range(K + 1):
		nsum = 0
		for x in range(k + 1):
			dp[i][k][x] += nsum
			dp[i][k][x] %= mod
			if x >= 0:
				nsum += dp[i - 1][k][x]
		nsum %= mod
ans = 0
for i in range(K + 1):
	ans += dp[N - 1][i][i]
	ans %= mod
print(ans)


(s, k) = input().split()
from random import randint
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
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:
			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)]
	for i in range(1, k + 1):
		r = i - 1
		c = 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(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 + 1):
		for j in range(k + 1):
			D[i][j] = (D0[i][j] + D1[i][j]) % mod
print(sum(D[0]) % mod)


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
from collections import Counter
C = Counter(ONES)
for numb in range(Z, -1, -1):
	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] += DP[i][j]
	DP = NDP
ANS = 0
for i in range(min(O, K) + 1):
	ANS += DP[i][0]
print(ANS % mod)


import sys
sys.setrecursionlimit(10 ** 7)
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
from collections import deque
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import lru_cache
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
	(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[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)
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(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)]
dp[0][0] = 1
for ai in a[::-1]:
	ndp = [[0] * M for _ in range(k + 1)]
	for j in range(k + 1):
		for l in range(M):
			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):
				ndp[j + i][l + i] += dp[j][l]
				ndp[j + i][l + i] %= MOD
	dp = ndp
ans = 0
for jj in range(k + 1):
	ans += dp[jj][0]
print(ans % MOD)


(s, k) = input().split()
K = int(k)
if s[-1] == '1':
	s += '0'
n = len(s)
ls = []
cnt = 0
for i in range(n):
	if s[i] == '0':
		ls.append(cnt)
		cnt = 0
	else:
		cnt += 1
l = len(ls)
sm = sum(ls)
mod = 998244353
dp = [[[0 for i in range(sm + 1)] for j in range(sm + 1)] for k in range(l + 1)]
dp[0][0][0] = 1
smprv = 0
for i in range(1, l + 1):
	num = ls[i - 1]
	for j in range(smprv + num, sm + 1):
		if j == smprv + num:
			dp[i][j][0] = 1
		for k in range(1, j + 1):
			x = 0
			for m in range(j + 1):
				if num >= m:
					x += dp[i - 1][j - m][k]
				else:
					x += dp[i - 1][j - m][k - (m - num)]
			dp[i][j][k] = x % mod
	smprv += num
ans = 0
for i in range(sm + 1):
	if i <= K:
		ans += dp[-1][-1][i]
		ans %= mod
print(ans)


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 5)
MOD = 998244353

def solve(S, K):
	numZeroes = S.count('0')
	ones = [0 for i in range(numZeroes + 1)]
	j = 0
	for x in S:
		if x == '0':
			j += 1
		else:
			assert x == '1'
			ones[j] += 1

	@lru_cache(maxsize=None)
	def numWays(i, usedK, extraOnes):
		if usedK == K and extraOnes == 0:
			return 1
		if i == 0:
			return 1
		ways = numWays(i - 1, usedK, extraOnes)
		for j in range(1, extraOnes + 1):
			ways += numWays(i - 1, usedK, extraOnes - j)
			ways %= MOD
		for j in range(1, ones[i] + 1):
			if usedK + j > K:
				break
			ways += numWays(i - 1, usedK + j, extraOnes + j)
			ways %= MOD
		return ways % MOD
	return numWays(len(ones) - 1, 0, 0) % MOD

def solve(S, K):
	numZeroes = S.count('0')
	numOnes = len(S) - numZeroes
	ones = [0 for i in range(numZeroes + 1)]
	j = 0
	for x in S:
		if x == '0':
			j += 1
		else:
			assert x == '1'
			ones[j] += 1
	K = min(K, numOnes)
	numWays = [[[None for extraOnes in range(numOnes + 1)] for usedK in range(K + 1)] for i in range(len(ones))]
	for i in range(len(ones)):
		numWays[i][K][0] = 1
	for usedK in range(K + 1):
		for extraOnes in range(numOnes + 1):
			numWays[0][usedK][extraOnes] = 1
	for i in range(len(ones)):
		for usedK in range(K, -1, -1):
			for extraOnes in range(usedK, -1, -1):
				if usedK == K and extraOnes == 0:
					continue
				if i == 0:
					continue
				ways = numWays[i - 1][usedK][extraOnes]
				for j in range(1, extraOnes + 1):
					ways += numWays[i - 1][usedK][extraOnes - j]
					ways %= MOD
				for j in range(1, ones[i] + 1):
					if usedK + j > K or extraOnes + j > numOnes:
						break
					ways += numWays[i - 1][usedK + j][extraOnes + j]
					ways %= MOD
				numWays[i][usedK][extraOnes] = ways % MOD
	return numWays[len(ones) - 1][0][0] % MOD
(S, K) = input().split()
S = list(S)
K = int(K)
print(solve(S, K))


(S, K) = input().split()
A = list(map(len, S.split('0')))
A[0] = 0
A.append(0)
N = len(A)
K = int(K)
K = min(K, S.count('1'))
MOD = 998244353
dp = [[[0] * (K + 1) for _ in [0] * (K + 1)] for _ in [0] * N]
dp[-1][0][0] = 1
for i in range(1, N):
	i = N - 1 - i
	for k in range(K + 1):
		for n in range(K + 1):
			dp[i][k][n] = sum(dp[i + 1][k][n:]) % MOD
			for a in range(1, A[i] + 1):
				if k - a < 0 or n - a < 0:
					break
				dp[i][k][n] += dp[i + 1][k - a][n - a]
				dp[i][k][n] %= MOD
ans = sum((dp[0][k][0] for k in range(K + 1)))
ans %= MOD
print(ans)


from sys import exit
MOD = 998244353
(s, K) = input().split()
K = min(int(K), s.count('1'))
if K == 0:
	print(1)
	exit()
a = []
cnt = 0
for i in range(len(s)):
	if s[i] == '0':
		a.append(cnt)
		cnt = 0
	else:
		cnt += 1
a.append(cnt)
a.reverse()
n = len(a)
dp = [[[0 for _ in range(K + 1)] for _ in range(K + 1)] for _ in range(n + 1)]
col = [[0 for _ in range(K + 1)] for _ in range(K + 1)]
dia = [[0 for _ in range(K + 1)] for _ in range(K + 1)]
dp[0][0][0] = 1
col[0][0] = 1
for j in range(K + 1):
	dia[j][j] = 1

def COL(j, k):
	if k == 0:
		return col[j][j]
	else:
		return col[j][j] - col[j][k - 1]

def DIA(i, j, k):
	if k == 0:
		return 0
	elif k > a[i - 1]:
		return dia[j - 1][k - 1] - dia[j - a[i - 1] - 1][k - a[i - 1] - 1]
	else:
		return dia[j - 1][k - 1]
for i in range(1, n + 1):
	for j in range(K + 1):
		for k in range(j + 1):
			dp[i][j][k] += COL(j, k)
			dp[i][j][k] += DIA(i, j, k)
			dp[i][j][k] %= MOD
	for j in range(K + 1):
		col[j][0] = dp[i][j][0]
		dia[j][0] = dp[i][j][0]
		for k in range(1, j + 1):
			col[j][k] = (col[j][k - 1] + dp[i][j][k]) % MOD
			dia[j][k] = (dia[j - 1][k - 1] + dp[i][j][k]) % MOD
ans = 0
for j in range(K + 1):
	ans += dp[n][j][0]
	ans %= MOD
print(ans)


sk = input().split()
s = sk[0]
K = int(sk[1])
mod = 998244353
x = [0]
for si in s:
	if si == '0':
		x.append(0)
	else:
		x[-1] += 1
while x:
	if x[-1] == 0:
		x.pop()
	else:
		break
x = x[::-1]
len_x = len(x)
ones = min(K, sum(x))
dp = [[] for _ in range(len_x + 1)]
for i in range(len_x + 1):
	dp[i] = [[0] * (ones + 1) for _ in range(ones + 1)]
dp[0][0][0] = 1
for (i, xi) in enumerate(x):
	cumsum_y = [[0] * (ones + 2) for _ in range(ones + 2)]
	cumsum_xy = [[0] * (ones + 2) for _ in range(ones + 2)]
	for j in range(ones + 1):
		for k in range(ones + 1):
			cumsum_y[j + 1][k + 1] = (cumsum_y[j][k + 1] + dp[i][j][k]) % mod
			cumsum_xy[j + 1][k + 1] = (cumsum_xy[j][k] + dp[i][j][k]) % mod
	for j in range(ones + 1):
		for k in range(j, ones + 1):
			dp[i + 1][j][k] += cumsum_y[k + 1][k + 1] - cumsum_y[j][k + 1]
			dp[i + 1][j][k] += cumsum_xy[j][k] - cumsum_xy[max(0, j - xi)][max(0, j - xi) + k - j]
			dp[i + 1][j][k] %= mod
ans = 0
for k in range(ones + 1):
	ans += dp[-1][0][k]
	ans %= mod
print(ans)


(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)


mod = 998244353
(S, K) = input().split()
a = [len(x) for x in S.split('0')]
K = min(int(K), sum(a) + 1)

def solve_naive():
	f = [[[0 for k in range(K + 1)] for j in range(K + 1)] for i in range(len(a) + 1)]
	for i in range(len(a) + 1):
		if i == 0:
			f[i][0][0] = 1
		else:
			for j in range(K + 1):
				for k in range(j + 1):
					f[i][j][k] += f[i - 1][j][k]
					f[i][j][k] %= mod
					for num in range(1, j - k + 1):
						if k + num > K:
							break
						f[i][j][k + num] += f[i - 1][j][k]
						f[i][j][k + num] %= mod
					for num in range(1, a[-i] + 1):
						if j + num > K:
							break
						f[i][j + num][k] += f[i - 1][j][k]
						f[i][j + num][k] %= mod
	ans = 0
	for num in range(K + 1):
		ans += f[len(a)][num][num]
		ans %= mod
	return ans

def solve():
	f = [[[0 for k in range(K + 1)] for j in range(K + 1)] for i in range(len(a) + 1)]
	for i in range(len(a) + 1):
		if i == 0:
			f[i][0][0] = 1
		else:
			for j in range(K + 1):
				cum2 = 0
				for k in range(j + 1):
					f[i][j][k] += f[i - 1][j][k]
					f[i][j][k] %= mod
					f[i][j][k] += cum2
					f[i][j][k] %= mod
					cum2 += f[i - 1][j][k]
			for k in range(K + 1):
				cum3 = 0
				for j in range(k, K + 1):
					if j < a[-i]:
						f[i][j][k] += cum3
						f[i][j][k] %= mod
						cum3 += f[i - 1][j][k]
					else:
						f[i][j][k] += cum3
						f[i][j][k] %= mod
						cum3 += f[i - 1][j][k] - f[i - 1][j - a[-i]][k]
	ans = 0
	for num in range(K + 1):
		ans += f[len(a)][num][num]
		ans %= mod
	return ans
print(solve())


(S, Kstring) = input().split()
K = int(Kstring)
lastZero = -1
segment = []
MOD = 998244353
N = len(S)
for i in range(N):
	if S[i] == '0':
		segment.append(i - lastZero - 1)
		lastZero = i
segment.append(N - 1 - lastZero)
M = len(segment)
No1 = N + 1 - M
partialSumSegment = []
for i in range(M):
	if partialSumSegment:
		partialSumSegment.append(segment[i] + partialSumSegment[-1])
	else:
		partialSumSegment.append(segment[i])
DP = []
DPSum = []
for i in range(M):
	DP.append([])
	DPSum.append([])
	for j in range(No1 + 2):
		DP[i].append([])
		DPSum[i].append([])
		for k in range(No1 + 2):
			DP[i][j].append(0)
			DPSum[i][j].append(0)
for j in range(No1 - partialSumSegment[M - 2] + 1):
	DP[M - 1][j][partialSumSegment[M - 2] + j] = 1
for j in range(No1 - partialSumSegment[M - 2] + 1):
	for k in range(partialSumSegment[M - 2] + j, -1, -1):
		DPSum[M - 1][j][k] = DPSum[M - 1][j][k + 1] + DP[M - 1][j][k]
for i in range(M - 2, -1, -1):
	for j in range(No1 + 1):
		Kmin = partialSumSegment[i - 1]
		if i == 0:
			Kmin = 0
		for k in range(No1, Kmin - 1, -1):
			DPCur = 0
			for l in range(1, segment[i] + 1):
				if j >= l and k + segment[i] - l <= No1 + 1:
					DPCur += DP[i + 1][j - l][k + segment[i] - l]
			if k + segment[i] <= No1:
				DPCur += DPSum[i + 1][j][k + segment[i]]
			DP[i][j][k] = DPCur % MOD
			DPSum[i][j][k] = (DPSum[i][j][k + 1] + DP[i][j][k]) % MOD
AnsSum = 0
for j in range(min(K, No1) + 1):
	AnsSum += DP[0][j][0]
if M == 1:
	print(1)
else:
	print(AnsSum % MOD)


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 998244353
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
(S, K) = SL()
K = int(K)
data = []
ones = 0
count = 0
for s in S:
	if s == '1':
		count += 1
		ones += 1
	else:
		data.append(count)
		count = 0
data.append(count)
data = data[::-1]
N = len(data)
K = min(K, ones)
dp = [[[0 for j in range(K + 1)] for k in range(K + 1)] for i in range(N)]
for i in range(N):
	dp[i][0][0] = 1
for k in range(min(data[0] + 1, K + 1)):
	dp[0][k][k] = 1
for i in range(1, N):
	for k in range(K + 1):
		for j in range(K + 1)[::-1]:
			if j == K:
				dp[i][k][j] = dp[i - 1][k][j]
				dp[i][k][j] %= MOD
			else:
				dp[i][k][j] = dp[i - 1][k][j] + dp[i][k][j + 1]
				dp[i][k][j] %= MOD
	a = data[i]
	if a:
		for k in range(K):
			q = deque([dp[i - 1][k][0]])
			temp = dp[i - 1][k][0]
			for j in range(1, K + 1):
				if k + j > K:
					break
				dp[i][k + j][j] += temp
				dp[i][k + j][j] %= MOD
				q.append(dp[i - 1][k + j][j])
				temp += dp[i - 1][k + j][j]
				if len(q) > a:
					temp -= q.popleft()
				temp %= MOD
ans = 0
for k in range(K + 1):
	ans += dp[-1][k][0]
	ans %= MOD
print(ans)


(s, k) = input().split()
(k, o, c, z, L, O) = (int(k), s.count('1') + 1, 0, 0, [], 998244353)
(M, r) = (min(o, k + 1), range)
for i in s:
	if i == '0':
		L += [c]
		c = 0
	else:
		c += 1
d = [[0] * M for _ in r(o)]
d[0][0] = 1
for i in L:
	D = [[0] * M for _ in r(o)]
	for j in r(o):
		for l in r(max(z + i - j, 0), o - j):
			m = max(l - i, 0)
			for p in r(min(j + 1, M - m)):
				D[j + l][p + m] = (D[j + l][p + m] + d[j][p]) % O
	z += i
	d = D
print(sum([sum(i) for i in d]) % O)


mod = 998244353
(S, K) = input().split()
a = []
c = 0
for i in range(len(S)):
	if S[i] == '0':
		a.append(c)
		c = 0
	else:
		c += 1
if S[-1] == '1':
	a.append(c)
a = a[::-1]
K = min(sum(a), int(K))
N = len(a)
dp = [[[0] * (K + 1) for _ in range(K + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
	for j in range(K + 1):
		for k in range(j + 1):
			for l in range(a[i] + 1):
				if j + l > K:
					break
				dp[i + 1][j + l][k + l] += dp[i][j][k]
				dp[i + 1][j + l][k + l] %= mod
			for l in range(1, k + 1):
				dp[i + 1][j][k - l] += dp[i][j][k]
				dp[i + 1][j][k - l] %= mod
ans = 0
for k in range(K + 1):
	ans += dp[N][k][0]
	ans %= mod
print(ans)


MOD = 998244353

def solve(s, k):
	one_count = []
	ones = 0
	for st in s:
		if st == '1':
			ones += 1
		else:
			one_count.append(ones)
			ones = 0
	one_count.append(ones)
	ss = sum(one_count)
	m = len(one_count)
	dp = [[[0] * (ss + 1) for _ in range(ss + 1)] for __ in range(m + 1)]
	dp[0][0][0] = 1
	for i in range(m):
		c = one_count[i]
		for j in range(ss + 1):
			for p in range(ss + 1):
				dp[i][j][p] %= MOD
				for q in range(ss + 1 - max(j, p)):
					dp[i + 1][j + q][p + q] += dp[i][j][p]
				for q in range(-c, 0):
					if j + q >= 0:
						dp[i + 1][j + q][p] += dp[i][j][p]
	res = sum([dp[m][0][p] for p in range(min(k + 1, ss + 1))])
	return res % MOD

def main():
	(s, k_) = input().split()
	k = int(k_)
	res = solve(s, k)
	print(res)

def test():
	assert solve('0101', 1) == 4
	assert solve('01100110', 2) == 14
	assert solve('1101010010101101110111100011011111011000111101110101010010101010101', 20) == 113434815
test()
main()


def main():
	mod = 998244353
	(s, k) = input().split()
	(k, n, o, cnt, z, zero_list) = (int(k), len(s), s.count('1') + 1, 0, 0, [])
	for i in range(n):
		if s[i] == '0':
			zero_list.append(cnt)
			cnt = 0
		else:
			cnt += 1
	m = min(o, k + 1)
	dp = [[0] * m for _ in [0] * o]
	dp[0][0] = 1
	for i in zero_list:
		dp2 = [[0] * m for _ in [0] * o]
		dp3 = [[0] for _ in [0] * o]
		for x in range(o):
			t = 0
			for y in range(min(m, o - x)):
				t = (t + dp[x + y][y]) % mod
				dp3[x].append(t)
		dp4 = [[0] * m for _ in [0] * o]
		for y in range(m):
			t = dp[0][y]
			for x in range(1, o):
				dp4[x - 1][y] = t
				t = (t + dp[x][y]) % mod
			dp4[o - 1][y] = t
		for j in range(z + i, o):
			for x in range(min(j - i + 1, m)):
				dp2[j][x] = (dp2[j][x] + dp3[j - x - i][min(o, x + 1)]) % mod
			for p in range(m):
				dp2[j][p] = (dp2[j][p] + dp4[j][p] - dp4[max(j - i, p - 1)][p]) % mod
		z += i
		dp = dp2
	print(sum([sum(i) for i in dp]) % mod)
main()