Problem:
 Score : 800 points    Problem Statement 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).        Sample Input 1 0101 1      Sample Output 1 4  Four strings, 0101 , 0110 , 1001 , and 1010 , can result.       Sample Input 2 01100110 2      Sample Output 2 14       Sample Input 3 1101010010101101110111100011011111011000111101110101010010101010101 20      Sample Output 3 113434815

Solution (Python):
import numpy as np


def solve(slots_array, K):
    MOD = 998244353
    dp = np.zeros((K+1, K+1), np.int64)
    dp[0][0] = 1
    for i in range(len(slots_array) - 1, -1, -1):
        new_dp = dp.copy()
        for j in range(K, -1, -1):
            for k in range(K-1, -1, -1):
                new_dp[j][k] += new_dp[j][k+1]
        new_dp %= MOD
        for t in range(1, slots_array[i] + 1):
            new_dp[t:, t:] += dp[:-t, :-t]
        dp = new_dp
    
    return np.sum(dp[:K+1, 0]) % MOD

def main():     
    S, K_str = input().split()
    K = int(K_str)

    slots = []
    index = 0
    while index < len(S):
        prev_index = index
        while index < len(S) and S[index] == '1':
            index += 1
        slots.append(index - prev_index)
        index += 1

    K = min(sum(slots) + 1, K)
    print(solve(np.array(slots, np.int64), K))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8(i8[:], i8)')(solve)
    cc.compile()

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


def solve(slots_array, K):
    MOD = 998244353
    dp = np.zeros((K+1, K+1), np.int64)
    dp[0][0] = 1
    for i in range(len(slots_array) - 1, -1, -1):
        new_dp = dp.copy()
        for j in range(K, -1, -1):
            for k in range(K-1, -1, -1):
                new_dp[j][k] += new_dp[j][k+1]
        new_dp %= MOD
        for t in range(1, slots_array[i] + 1):
            new_dp[t:, t:] += dp[:-t, :-t]
        dp = new_dp
    
    return np.sum(dp[:K+1, 0]) % MOD

def main():     
    S, K_str = input().split()
    K = int(K_str)

    slots = []
    index = 0
    while index < len(S):
        prev_index = index
        while index < len(S) and S[index] == '1':
            index += 1
        slots.append(index - prev_index)
        index += 1

    K = min(sum(slots) + 1, K)
    print(solve(np.array(slots, np.int64), K))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', 'i8(i8[:], i8)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)
    




if __name__ == "__main__":
    main()

Solution (Python):
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)

Solution (Python):
from itertools import groupby
import numpy as np


def solve(s, k):
    sgrp = [len(list(itr)) for c, itr in groupby(s)]
    if len(sgrp) == 1:
        return 1

    one_bucket = []
    MOD = 998244353

    if s[0] == '1':
        one_bucket.append(sgrp[0])
        sgrp = sgrp[1:]
    else:
        one_bucket.append(0)

    cur = 0
    for l in sgrp:
        if cur == 0:
            one_bucket.extend([0] * (l - 1))
        else:
            one_bucket.append(l)
        cur ^= 1

    k = min(k, sum(one_bucket))
    dp = np.zeros((k + 1, k + 1), dtype=np.int64)
    dp[0, 0] = 1

    for i, c in enumerate(one_bucket):
        ndp = np.add.accumulate(dp, axis=0)
        if c > 0:
            for j in range(1, c + 1):
                ndp[:, j:] += dp[:, :-j]
            ndp = np.tril(ndp)
        dp = ndp % MOD

    return np.diag(dp).sum() % MOD


s, k = input().split()
k = int(k)

print(solve(s, k))

Solution (Python):
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)

Solution (Python):
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_naive())

Solution (Python):
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())

Solution (Python):






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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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 jl in range(z+i, one):
            for x in range(i, min(one, jl+1, mm+i+1)):
                dp2[jl][x-i] = (dp2[jl][x-i]+sum([dp[jl-x+p][p]
                                                  for p in range(min(one, x-i+1))])) % mod
            for p in range(min(one, mm+1)):
                dp2[jl][p] = (dp2[jl][p]+sum([dp[jl-l][p]
                                              for l in range(min(one, i, jl-p+1))])) % mod
        z += i
        dp = dp2
    print(sum([sum(i) for i in dp]) % mod)


main()

Solution (Python):
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)

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]

dp=[[0 for i in range(K+1)] for j in range(K+1)]
plus=[[0 for j in range(K+1)] for k in range(K+1)]
minus=[[0 for j in range(K+1)] for k in range(K+1)]

for j in range(K+1):
    dp[j][j]=1
    plus[j][j]=1
    minus[j][j]=1

for k in range(K+1):
    for j in range(1,K+1):
        plus[j][k]+=plus[j-1][k]

for j in range(K+1):
    for k in range(1,K+1):
        minus[j][k]+=minus[j][k-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])
            if max(0,M)+j==0:
                ndp[j][k]+=plus[K][k]
            else:
                ndp[j][k]+=plus[K][k]-plus[(max(0,M))+j-1][k]
            if min(K-k,-M)>0:
                ndp[j][k]+=minus[j][k+min(K-k,-M)]-minus[j][k]
            ndp[j][k]%=mod
    dp=ndp
    for j in range(K+1):
        for k in range(K+1):
            plus[j][k]=ndp[j][k]
            minus[j][k]=ndp[j][k]

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

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


print(dp[0][0])

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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])
            ndp[j][k]=sum(dp[j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[j][k+l] for l in range(1,min(K-k,-M)+1))
            ndp[j][k]%=mod
    dp=ndp

print(dp[0][0])

Solution (Python):
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 k in range(m+1)]

for j in range(K+1):
    dp[m][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):
    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])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])

Solution (Python):
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 k in range(m+1)]

for j in range(K+1):
    dp[m][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):
    for j in range(K+1):
        for k in range(min(b[i],K)+1):
            M=max(k-j,-a[i])
            dp[i][j][k]=sum(dp[i+1][j+l][k] for l in range(max(0,M),K-j+1))+sum(dp[i+1][j][k+l] for l in range(1,min(K-k,-M)+1))
            dp[i][j][k]%=mod

print(dp[0][0][0])

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):


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