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 _120 {
      public static void main(String[] args) {
          MyScanner sc = new MyScanner();
          PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
          int t = 1;
          long [][] table = new long[5001][5001];
          for (int i = 1; i <= 5000; i++) {
              for (int j = 0; j <= i; j++) {
                  if (j == 0 || j == i) table[i][j] = 1;
                  else {
                      table[i][j] = (table[i - 1][j] + table[i - 1][j - 1]) % mod;
                  }
              }
          }
          while (t-- > 0) {
              int n = sc.nextInt();
              int k = sc.nextInt();
              String s = sc.next();
              ArrayList<Integer> a = new ArrayList<>();
              for (int i = 0; i < n; i++) {
                  if (s.charAt(i) == '1') {
                      a.add(i);
                  }
              }
              int sz = a.size();
              if (sz < k) {
                  out.println(1);
                  continue;
              }
              int [] after = new int[n];
              int [] before = new int[n];
              Arrays.fill(after, -1); Arrays.fill(before, -1);
              int cur = 0;
              for (int i = 0; i < n; i++) {
                  if (s.charAt(i) == '1') {
                      before[i] = cur;
                      cur = 0;
                  } else {
                      ++cur;
                  }
              }
              cur = 0;
              for (int i = n - 1; i >= 0; i--) {
                  if (s.charAt(i) == '1') {
                      after[i] = cur;
                      cur = 0;
                  } else {
                      ++cur;
                  }
              }
              int [][] len = new int[sz][sz];
              int [][] ones = new int[sz][sz];
              for (int i = 0; i < sz; i++) {
                  for (int j = i; j < sz; j++) {
                      if (i == j) {
                          len[i][j] = before[a.get(i)] + after[a.get(i)] + 1;
                      } else {
                          len[i][j] = a.get(j) - a.get(i) + 1 + before[a.get(i)] + after[a.get(j)];
                      }
                      ones[i][j] = j - i + 1;
                  }
              }
              long res = 1;
              for (int l = 1; l <= Math.min(k, sz); l++) {
                  for (int i = 0; i <= sz - l; i++) {
                      int j = i + l - 1;
                      if (l == 1) {
                          res = (res + table[len[i][i]][ones[i][i]] - 1) % mod;
                          if (res < 0) res += mod;
                          continue;
                      }
                      res = (res + table[len[i][j]][ones[i][j]]) % mod;
                      res = (res - table[len[i][j - 1]][ones[i][j - 1]]) % mod;
                      if (res < 0) res += mod;
                      res = (res - table[len[i + 1][j]][ones[i + 1][j]]) % mod;
                      if (res < 0) res += mod;
                      if (l == 2) {
                          res = (res + 1) % mod;
                      } else {
                          res = (res + table[len[i + 1][j - 1]][ones[i + 1][j - 1]]) % mod;
                      }
                  }
              }
              out.println(res);
          }
          out.close();
      }
  
      static long mod = (long) 998244353;
  
  
  
      static void sort(int[] a) {
          ArrayList<Integer> q = new ArrayList<>();
          for (int i : a) q.add(i);
          Collections.sort(q);
          for (int i = 0; i < a.length; i++) a[i] = q.get(i);
      }
  
      static void sort(long[] a) {
          ArrayList<Long> q = new ArrayList<>();
          for (long i : a) q.add(i);
          Collections.sort(q);
          for (int i = 0; i < a.length; i++) a[i] = q.get(i);
      }
  
  
      //-----------MyScanner class for faster input----------
      public static class MyScanner {
          BufferedReader br;
          StringTokenizer st;
  
          public MyScanner() {
              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;
          }
  
  
      }
  
  }