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 Codeforces
  {
      public static void main(String args[])throws Exception
      {
          BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
          StringBuilder sb=new StringBuilder();
          String s[]=bu.readLine().split(" ");
          int n=Integer.parseInt(s[0]),k=Integer.parseInt(s[1]);
  
          char c[]=bu.readLine().toCharArray();
          ArrayList<Integer> one=new ArrayList<>();
          int i;
          for(i=0;i<n;i++)
          if(c[i]=='1') one.add(i);
          if(k==0 || one.size()<k) {System.out.println(1); return;}
  
          long f[]=new long[n+1],in[]=new long[n+1];
          f[0]=in[0]=1;
          for(i=1;i<=n;i++) f[i]=f[i-1]*i%M;
          in[n]=power(f[n],M-2);
          for(i=n-1;i>0;i--) in[i]=in[i+1]*(i+1)%M;
  
          long ans=0;
          for(i=0;i+k<=one.size();i++)
          {
              int z=0,o=k,j;
              for(j=i+1;j<i+k;j++)
              z+=one.get(j)-one.get(j-1)-1;
              if(i==0) z+=one.get(i);
              else z+=one.get(i)-one.get(i-1)-1;
              if(i+k<one.size()) z+=one.get(i+k)-one.get(i+k-1)-1;
              else z+=n-one.get(i+k-1)-1;
  
              //System.out.println(z+" "+o);
              long cur=f[z+o]*in[o]%M*in[z]%M;
              if(i>0)
              {
                  o--;
                  z=0;
                  for(j=i;j<i+k;j++) z+=one.get(j)-one.get(j-1)-1;
  
                  cur-=f[z+o]*in[o]%M*in[z]%M;
                  cur=(cur+M)%M;
              }
              //System.out.println(cur);
              ans=(ans+cur)%M;
          }
          System.out.println(ans);
      }
  
      static long M=998244353;
      static long power(long a,long b)
      {
          long res=1;
          while(b!=0)
          {
              if(b%2==1) res=res*a%M;
              b>>=1;
              a=a*a%M;
          }
          return res;
      }
  }