output_description: Find the number of strings, modulo 998244353, that can result from applying
  the operation on S between 0 and K times (inclusive).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S K
attempt: P = 998244353
  S, K = input().split()
  N = S.count("0") + 1
  A = [len(a) for a in S.split("0")][::-1]
  K = int(K)
  X = [[0] * N for _ in range(N)]
  X[0][0] = 1
  for a in A:
      nX = [[0] * N for _ in range(N)]
      Y = [x[:] for x in X]
      for i in range(N - 1)[::-1]:
          for j in range(N):
              Y[i][j] += Y[i + 1][j]
              if Y[i][j] >= P:
                  Y[i][j] -= P
      Z = [[0] * (N + 1)] + [[0] + x[:] for x in X]
      for i in range(N):
          for j in range(N):
              Z[i + 1][j + 1] = Z[i][j] + X[i][j]
              if Z[i + 1][j + 1] >= P:
                  Z[i + 1][j + 1] -= P
  
      for i in range(N):
          for j in range(N):
              nX[i][j] += Y[i][j]
              t = min(a, i, j)
              nX[i][j] += Z[i][j] - Z[i - t][j - t]
              nX[i][j] %= P
      X = nX
  print(sum(X[0][: K + 1]) % P)
  
problem_description: 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.
samples: [{"input": "0101 1", "output": "4\n    \n\nFour strings, `0101`, `0110`, `1001`, and `1010`, can result.\n\n* * *"}, {"input": "01100110 2", "output": "14\n    \n\n* * *"}, {"input": "1101010010101101110111100011011111011000111101110101010010101010101 20", "output": "113434815"}]