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.io.*;
  import java.util.*;
   
  public class Solution extends PrintWriter {
      
      
      void solve() {
          pre();
          int n = sc.nextInt();
          int k = sc.nextInt();
          String s = sc.nextString();
          if(k == 0) {
              println(1);
              return;
          }
          int cnt = 0;
          for(int i = 0; i < n; i++) {
              if(s.charAt(i) == '1') cnt++;
          }
          if(cnt < k) {
              println(1);
              return;
          }
          long ans = 0L;
          for(int i = 0; i < n; i++) {
                  cnt = 0;
                  int j = i;
                  while(j < n) {
                      if(s.charAt(j) == '1') {
                          if(cnt == k) break;
                          cnt++;
                      }
                      j++;
                  }
                  if(j == n && cnt == k) {
                      ans += C(j-i, k);
                      if(ans >= M) ans -= M;
                      break;
                  } else if(cnt == k) {
                      if(s.charAt(i) == '0') {
                          ans += C(j-i-1, k-1);                        
                      } else {
                          ans += C(j-i-1, k);
                      }
                      if(ans >= M) ans -= M;
                  }
          }
          println(ans);
      }
      
      int MX = 5000;
      long[] fac = new long[MX+1];
      long[] fac_inv = new long[MX+1];
      long[] inv = new long[MX+1];
      
      long M = 998244353L;
   
      long C(int n, int k) {
          if(k > n) return 0L;
          long  c = (fac_inv[k] * fac_inv[n - k]) % M;
          c = (c * fac[n]) % M;
          return c;
      }
   
      
      void pre() {
          inv[1] = 1L;
          for(int i = 2; i <= MX; i++) 
              inv[i] = M - (M/i) * inv[(int)(M%i)] % M;
          fac[0] = 1L;
          fac_inv[0] = 1L;
          for(int i = 1; i <= MX; i++) {
              fac[i] = (fac[i-1]*i)%M;
              fac_inv[i] = (fac_inv[i-1]*inv[i])%M;
          }
      }
      
          
  //  Main() throws FileNotFoundException { super(new File("output.txt")); }
  //  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    Solution() { super(System.out); }
    InputReader sc = new InputReader(System.in);
    static class InputReader {
        InputReader(InputStream in) { this.in = in; } InputStream in;
        
        private byte[] buf = new byte[16384];
        private int    curChar;
        private int    numChars;
        
   
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
  
   
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
   
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
   
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
   
      public static void main(String[] $) {
          new Thread(null, new Runnable() {
              public void run() {
                  long start = System.nanoTime();
                  try {Solution solution = new Solution(); solution.solve(); solution.flush();} 
                  catch (Exception e) {e.printStackTrace(); System.exit(1);}
                  System.err.println((System.nanoTime()-start)/1E9);
              }
          }, "1", 1 << 27).start();
   
      }
  }