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.Closeable;
  import java.io.DataInputStream;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.util.Arrays;
  
  public class D {
      static final long MODULO = 998244353;
  
      public static void main(String[] args) throws IOException {
          FastScanner scanner = new FastScanner();
          int n = scanner.nextInt();
          int k = scanner.nextInt();
          String str = scanner.next();
          int[] zeros = new int[(int) str.chars().filter(i -> i == '1').count() + 1];
          if (k > zeros.length - 1 || k == 0) {
              System.out.println(1);
              return;
          }
          ModularHelper mod = new ModularHelper(MODULO, 1, 1);
  
          {
              int ptr = 0;
              for (char c : str.toCharArray())
                  if (c == '0') zeros[ptr]++;
                  else ptr++;
          }
  
          int[] sums = new int[zeros.length];
          sums[0] = zeros[0];
          for (int i = 1; i < sums.length; i++) sums[i] = zeros[i] + sums[i - 1];
  
          long ans = mod.nCr(k + sums[k], k);
          for (int i = 1; i + k < sums.length; i++) {
              long temp1 = mod.nCr(k + sums[k + i] - sums[i - 1], k);
              long temp2 = mod.nCr(k - 1 + sums[k + i - 1] - sums[i - 1], k - 1);
              ans = mod.subtract(mod.add(ans, temp1), temp2);
          }
          System.out.println(ans);
      }
  
  
      /**
       * You MUST guarantee the divisor is a prime number or co-prime with all the numbers you are going to divide by.
       */
      private static class ModularHelper {
          final long[] invCache;
          final long[] factoCache;
          int factoCachePtr;
          final long divisor;
  
          public ModularHelper(long divisor, int invCache, int factoCache) {
              this.divisor = divisor;
              this.invCache = new long[invCache];
              this.factoCache = new long[factoCache];
              this.factoCache[0] = 1;
              factoCachePtr = 1;
          }
  
          public long add(long x, long y) { return ((x % divisor) + (y % divisor)) % divisor; }
  
          public long subtract(long x, long y) {
              long temp = (x % divisor) - (y % divisor);
              return temp < 0 ? temp + divisor : temp % divisor;
          }
  
          public long multiply(long x, long y) { return ((x % divisor) * (y % divisor)) % divisor; }
  
          public long factorial(long x) {
              if (x < factoCache.length) {
                  for (; factoCachePtr <= x; factoCachePtr++) factoCache[factoCachePtr] = multiply(factoCache[factoCachePtr - 1], factoCachePtr);
                  return factoCache[(int) x];
              } else {
                  long temp = factorial(factoCache.length - 1);
                  for (long i = temp + 1; i <= x; i++) temp = multiply(temp, i);
                  return temp;
              }
          }
  
          public long power(long x, long y) {
              if (y == 0) return 1;
              long p = power(x, y / 2) % divisor;
              p = (p * p) % divisor;
              return (y % 2 == 0) ? p : (x * p) % divisor;
          }
  
          /**
           * Credits: https://www.geeksforgeeks.org/fermats-little-theorem/
           */
          public long divide(long x, long y) { return ((x % divisor) * (inverse(y) % divisor)) % divisor; }
  
          public long inverse(long x) {
              if (x < invCache.length) {
                  if (invCache[(int) x] != 0) return invCache[(int) x];
                  else return invCache[(int) x] = power(x, divisor - 2);
              } else return power(x, divisor - 2);
          }
  
          public long nCr(long n, long r) { return divide(divide(factorial(n), factorial(r)), factorial(n - r)); }
      }
  
      /**
       * Credits: https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
       */
      private static class FastScanner implements Closeable {
          final private int BUFFER_SIZE = 1 << 16;
          private DataInputStream din;
          private byte[] buffer;
          private int bufferPointer, bytesRead;
  
          public FastScanner() {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public FastScanner(String file_name) throws IOException {
              din = new DataInputStream(new FileInputStream(file_name));
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
  
          public String readLine() throws IOException {
              byte[] buf = new byte[64];
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n' || c == '\r') {
                      if (cnt != 0) {
                          break;
                      } else {
                          continue;
                      }
                  }
                  buf[cnt++] = (byte) c;
              }
              return new String(buf, 0, cnt);
          }
  
          public String next() throws IOException {
              return next(32);
          }
  
          public String next(int len) throws IOException {
              byte[] buf = new byte[len];
              int ptr = 0;
              byte c = read();
              while (c <= ' ') c = read();
              do {
                  if (ptr == buf.length) {
                      buf = Arrays.copyOf(buf, buf.length << 1);
                  }
                  buf[ptr++] = c;
              } while ((c = read()) > ' ');
              if (buf.length == ptr) return new String(buf);
              return new String(Arrays.copyOf(buf, ptr));
          }
  
          public int nextInt() throws IOException {
              int ret = 0;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg) return -ret;
              return ret;
          }
  
          public long nextLong() throws IOException {
              long ret = 0;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg) return -ret;
              return ret;
          }
  
          public double nextDouble() throws IOException {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ') c = read();
              boolean neg = (c == '-');
              if (neg) c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (c == '.') {
                  while ((c = read()) >= '0' && c <= '9') {
                      ret += (c - '0') / (div *= 10);
                  }
              }
              if (neg) return -ret;
              return ret;
          }
  
          private void fillBuffer() throws IOException {
              bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
              if (bytesRead == -1) buffer[0] = -1;
          }
  
          private byte read() throws IOException {
              if (bufferPointer == bytesRead) fillBuffer();
              return buffer[bufferPointer++];
          }
  
          @Override
          public void close() throws IOException {
              if (din == null) return;
              din.close();
          }
      }
  }
  