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
  import heapq
  from bisect import bisect_left
  from collections import Counter, deque, defaultdict
  input = lambda: sys.stdin.readline().rstrip("\r\n")
  sys.setrecursionlimit(300005)
  LOGN = 20
  INF = 10 ** 9 + 5
  # MOD = 10 ** 9 + 7
  MOD = 998244353
  # ============================ START OF MY CODE ============================
  
  class nCk:
      def __init__(self, maxn, mod):
          self.mod = mod
          self.fact = fact = [1 for _ in range(maxn + 1)]
          self.temp = temp = [1 for _ in range(maxn + 1)]
          self.invs = invs = [1 for _ in range(maxn + 1)]
          for i in range(2, maxn + 1):
              fact[i] = fact[i - 1] * i % mod
              temp[i] = (- temp[mod % i] * (mod // i)) % mod
              invs[i] = invs[i - 1] * temp[i] % mod
  
      def get(self, n, k):
          if not 0 <= k <= n:
              return 0
          return (self.fact[n] * self.invs[k] % self.mod) * self.invs[n - k] % self.mod
  
  def solve():
      N, K = map(int, input().split())
      S = input()
      if S.count('1') < K or K == 0:
          print(1)
          return
  
      nck = nCk(5001, MOD)
      ans = left = 0
      cur_ones = 0
      for right in range(N):
          cur_ones += int(S[right])
          while cur_ones > K:
              cur_ones -= int(S[left])
              left += 1
          if S[right] == '1' and right - left >= cur_ones:
              ans += nck.get(right - left, cur_ones)
          if S[right] != '1' and right - left >= cur_ones - 1 >= 0:
              ans += nck.get(right - left, cur_ones - 1)
          ans %= MOD
      print((ans + 1) % MOD)
  
  if __name__ == "__main__":
      solve()
  