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: 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
  
  # print (ori)
  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]
  
      # 1を追加する
      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
  
      # xを使用する
  
      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
  
      # print (dp[i])
  
  ans = 0
  for i in range(K + 1):
      ans += dp[N - 1][i][i]
      ans %= mod
  print(ans)
  
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"}]