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 java.util.*;
  import java.io.*;
  
  public class Main {
      // For fast input output
      static class FastReader {
          BufferedReader br;
          StringTokenizer st;
  
          public FastReader() {
              try {
                  br = new BufferedReader(
                          new FileReader("input.txt"));
                  PrintStream out = new PrintStream(new FileOutputStream("output.txt"));
                  System.setOut(out);
              } catch (Exception e) {
                  br = new BufferedReader(new InputStreamReader(System.in));
              }
          }
  
          String next() {
              while (st == null || !st.hasMoreElements()) {
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              }
              return st.nextToken();
          }
  
          int nextInt() {
              return Integer.parseInt(next());
          }
  
          long nextLong() {
              return Long.parseLong(next());
          }
  
          double nextDouble() {
              return Double.parseDouble(next());
          }
  
          String nextLine() {
              String str = "";
              try {
                  str = br.readLine();
              } catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }
      }
  
      // end of fast i/o code
      public static void main(String[] args) {
          FastReader reader = new FastReader();
  
          int n = reader.nextInt();
          int k = reader.nextInt();
          long mod = 998244353;
  
          String s = reader.nextLine();
          long factorial[] = new long[5001];
          long prev = 1;
          factorial[0] = 1;
          for (int i = 1; i <= 5000; i++) {
              factorial[i] = (i * prev) % mod;
              prev = factorial[i];
          }
  
          int curr_len = 0;
          boolean last = false;
  
          int start = 0;
          int ones = 0;
          long ans = 0;
          long current;
          int end = 0;
  
          if (k == 0) {
              System.out.println("1");
              return;
          }
  
          for (end = 0; end < n; end++) {
              if (s.charAt(end) == '1') {
                  ones++;
              }
              if (ones > k) {
  
                  // adding something in ans
                  current = (factorial[end - start] * fast_pow(factorial[k], mod - 2, mod)) % mod;
                  current = (current * fast_pow(factorial[end - start - k], mod - 2, mod)) % mod;
                  // System.out.println(current + "<-> "+start+" "+end+" "+factorial[end-start]);
                  ans = (ans + current) % mod;
  
                  while (start < n && ones > k) {
                      if (s.charAt(start) == '1') {
                          start++;
                          ones--;
                          break;
                      }
                      start++;
                  }
  
                  current = (factorial[end - start] * fast_pow(factorial[ones - 1], mod - 2, mod)) % mod;
                  current = (current * fast_pow(factorial[end - start - (ones - 1)], mod - 2, mod)) % mod;
                  // System.out.println(current + "<- "+start+" "+end);
                  ans = (ans - current + mod) % mod;
  
                  // System.out.println(ans+"<->");
              }
          }
          if (ones == k) {
              current = (factorial[end - start] * fast_pow(factorial[ones], mod - 2, mod)) % mod;
              current = (current * fast_pow(factorial[end - start - ones], mod - 2, mod)) % mod;
              // System.out.println(current + "<-> "+start+" "+end+" "+factorial[end-start]+"
              // "+ones+" "+(end-start - ones));
              ans = (ans + current) % mod;
          }
  
          if(ans==0 && ones<k){
              ans = 1;
          }
          System.out.println(ans);
      }
  
      static long fast_pow(long a, long b, long mod) {
          if (b == 0) {
              return 1L;
          }
          // if(b==1){
          // return a;
          // }
          if (b % 2 == 1) {
              return (a * fast_pow(a, b - 1, mod)) % mod;
          } else {
              return fast_pow((a * a) % mod, b / 2, mod);
          }
      }
  }