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.Scanner;
  
  public class Main {
      
      static final long MOD = 998244353;
  
      public static void main(String[] args) {
      
          var sc = new Scanner(System.in);
          
          int n = Integer.parseInt(sc.next());
          int k = Integer.parseInt(sc.next());
          String s = sc.next();
          
          if(k == 0){
              System.out.println(1);
              return;
          }else if(k == 1){
              long ans = 1;
              for(int i = 0; i < n; i++){
                  if(s.charAt(i) == '0') continue;
                  int l = i;
                  int r = i;
                  while(0 < l && s.charAt(l-1) == '0'){
                      l--;
                  }
                  while(r < n-1 && s.charAt(r+1) == '0'){
                      r++;
                  }
                  ans += r-l;
              }
              System.out.println(ans);
              return;
          }
          
          long ans = 1;
          int l = 0;
          int r = 0;
          int count = s.charAt(0) == '0' ? 0 : 1;
          while(true){
              int r2 = 0;
              while(r < n-1 && (count < k || s.charAt(r+1) == '0')){
                  r++;
                  if(s.charAt(r) == '1'){
                      count++;
                      r2 = r;
                  }
              }
              if(count < k) break;
              
              if(l == 0){
                  ans += combination(r-l+1, count) - 1;
              }else{
                  if(r-l+1 > count){
                      ans += combination(r-l+1, count);
                      if(r2-l+1 >= count){
                          ans -= combination(r2-l+1, count);
                      }
                      if(r2-l >= count){
                          ans += combination(r2-l, count);
                      }
                  }
              }
              
              if(r == n-1) break;
              while(l < r && count == k){
                  if(s.charAt(l) == '1'){
                      count--;
                  }
                  l++;
              }
          }
          ans %= MOD;
          System.out.println(ans);
      }
      
      static long combination(long n, long r){
          if(n-r < r) r = n-r;
          long x = 1;
          long y = 1;
          for(int i = 0; i < r; i++){
              x *= n-i;
              x %= MOD;
              y *= i+1;
              y %= MOD;
          }
          x *= modinv(y);
          x %= MOD;
          return x;
      }
      
      static long modinv(long a){
          long b = MOD;
          long u = 1;
          long v = 0;
          long t, tmp;
          while(b != 0){
              t = a/b;
              a -= t*b;
              tmp = a;
              a = b;
              b = tmp;
              u -= t*v;
              tmp = u;
              u = v;
              v = tmp;
          }
          u %= MOD;
          if(u < 0) u += MOD;
          return u;
      }
  }