description: You are given a binary string (i. e. a string consisting of characters 0 and/or 1) s of length n. You can perform the following operation with the string s at most once: choose a substring (a contiguous subsequence) of s having exactly k characters 1 in it, and shuffle it (reorder the characters in the substring as you wish).
  
  Calculate the number of different strings which can be obtained from s by performing this operation at most once.
  
  Input
  
  The first line contains two integers n and k (2 ≤ n ≤ 5000; 0 ≤ k ≤ n).
  
  The second line contains the string s of length n, consisting of characters 0 and/or 1.
  
  Output
  
  Print one integer — the number of different strings which can be obtained from s by performing the described operation at most once. Since the answer can be large, output it modulo 998244353.
  
  Examples
  
  Input
  
  
  7 2
  1100110
  
  
  Output
  
  
  16
  
  
  Input
  
  
  5 0
  10010
  
  
  Output
  
  
  1
  
  
  Input
  
  
  8 1
  10001000
  
  
  Output
  
  
  10
  
  
  Input
  
  
  10 8
  0010011000
  
  
  Output
  
  
  1
  
  Note
  
  Some strings you can obtain in the first example:
  
    * to obtain 0110110, you can take the substring from the 1-st character to the 4-th character, which is 1100, and reorder its characters to get 0110; 
    * to obtain 1111000, you can take the substring from the 3-rd character to the 7-th character, which is 00110, and reorder its characters to get 11000; 
    * to obtain 1100101, you can take the substring from the 5-th character to the 7-th character, which is 110, and reorder its characters to get 101. 
  
  
  
  In the second example, k = 0 so you can only choose the substrings consisting only of 0 characters. Reordering them doesn't change the string at all, so the only string you can obtain is 10010.
solution: 
  import sys
  from sys import stdin
  from collections import deque
  
  def modfac(n, MOD):
   
      f = 1
      factorials = [1]
      for m in range(1, n + 1):
          f *= m
          f %= MOD
          factorials.append(f)
      inv = pow(f, MOD - 2, MOD)
      invs = [1] * (n + 1)
      invs[n] = inv
      for m in range(n, 1, -1):
          inv *= m
          inv %= MOD
          invs[m - 1] = inv
      return factorials, invs
  
  
  def nCr(n,r):
      return fac[n] * inv[n-r] * inv[r] % mod
  
  mod = 998244353
  fac,inv = modfac(10000,mod)
  
  tt = 1 #int(stdin.readline())
  
  ANS = []
  
  for loop in range(tt):
  
      n,k = map(int,stdin.readline().split())
      s = list(stdin.readline()[:-1])
  
      ssum = 0
      for i in s:
          ssum += int(i)
      if ssum < k or k == 0:
          print (1)
          sys.exit()
  
      ans = 1
  
      q = deque([])
      qsum = 0
  
      for i in range(n):
          q.append(int(s[i]))
          qsum += int(s[i])
  
          while len(q) > 0 and qsum > k:
              qsum -= q.popleft()
  
          zero = len(q) - qsum
          one = qsum
  
          if s[i] == "0":
              one -= 1
          else:
              zero -= 1
  
          if one < 0 or zero < 0:
              continue
          
          #print (i,one,zero)
          ans += nCr(one+zero,one)
          ans %= mod
  
      ANS.append(str(ans % mod))
  
  #print (nCr(1,0))
      
  print ("\n".join(ANS))
  