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.
5 2
00011
 5 4
11011
 81 5
100000101000000011001101010100001010111000000110000000001000101101111000001000110
 4 3
1011
 47 25
11110011111001110100101010011000110111011011101
 291 159
011001110111110110001111000110001001111100010001011000110100110010001101100110111010101111100111110000110111001100111010001000011001010011011100101000101011010110010011010100100101111010111000001011110101001011101110100100111110011001101010001110110101010101100011101110111000011111011001110
 459 15
101010101010101010101010101010101010101010101111111111111111111111010101010101010101010101011111111111111111111101010101010101010101111111111111111111111101010101010101010111111111111111111111111101010101010101111111111111111111111111110110101010101011111111111111111111111111111001000111111111111111111111111111110000011111111111111111111111111111000001111111111111111111111111111100001111111111111111111111111111100111111111111111111111111111110111111111111
 105 58
110101000111100000011011011101110100001000110011010101100010111001011111010010111101011011010110011011110
 52 11
0110011111001000010000100010010001010100000100110100

10
 5
 187538
 4
 314445058
 1
 0
 132732930
 478323746

// package c1622;

import java.io.File;
import java.lang.invoke.MethodHandles;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

//
// Educational Codeforces Round 120 (Rated for Div. 2) 2021-12-27 06:35
// D. Shuffle
// https://codeforces.com/contest/1622/problem/D
// time limit per test 2 seconds; memory limit per test 512 megabytes
// public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
//
// You are given a binary string (i.?e. a string consisting of characters and/or ) s of length n.
// You can perform the following operation with the string s : choose a substring (a contiguous
// subsequence) of s having k characters 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 and/or .
//
// 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.
//
// Example
/*
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 , you can take the substring from the 1-st character to the 4-th character, which is
//    , and reorder its characters to get ;
//  * to obtain , you can take the substring from the 3-rd character to the 7-th character, which is
//    , and reorder its characters to get ;
//  * to obtain , you can take the substring from the 5-th character to the 7-th character, which is
//    , and reorder its characters to get .
//
// In the second example, k = 0 so you can only choose the substrings consisting only of characters.
// Reordering them doesn't change the string at all, so the only string you can obtain is .
//
public class C1622D {
  static final int MOD = 998244353;
  static final Random RAND = new Random();

  static int solve(String s, int k) {
    if (k == 0) {
      return 1;
    }
    int n = s.length();
    List<Integer> ones = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      if (s.charAt(i) == '1') {
        ones.add(i);
      }
    }
    if (ones.size() < k) {
      return 1;
    }

    int[][] pascal = computePascal(n);
    // System.out.println(Utils.trace(pascal, true));
    // For any k-substring, split into head and tail by the last 1
    //
    //     _________k-substring_______
    //   1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1
    //     ------------------- -------
    //              ^             ^
    //            head          tail
    long ans = 0;
    for (int i = k-1; i < ones.size(); i++) {
      // [ib, ie) of current k-substring
      int is = ones.get(i);
      int ib = i < k ? 0 : ones.get(i-k) + 1;
      int ie = i + 1 < ones.size() ? ones.get(i+1) : n;
      // length of head and tail respectively
      int h = is - ib;
      int t = ie - is;
      int m = h + t;
      // Add new contribution to ans
      if (i == k - 1) {
        ans = (ans + pascal[m][k]) % MOD;
      } else {
        // case 1: allocate the one at index is to head if possible
        if (h >= k) {
          ans = (ans + pascal[h][k]) % MOD;
        }
        // case 2: a single 1 in tail but not at is
        if (t > 1) {
          ans = (ans + (long)(t-1)*pascal[h][k-1]) % MOD;
        }
        // case 3: r > 1 1s in tail, (k-r) in head
        for (int r = 2; r <= Math.min(t, k); r++) {
          ans = (ans + (long)pascal[t][r] * pascal[h][k-r]) % MOD;
        }
      }
    }
    return (int) ans;
  }

  static int[][] computePascal(int n) {
    int[][] pascal = new int[n+1][n+1];
    pascal[0][0] = 1;
    for (int i = 1; i <= n; i++) {
      pascal[i][0] = 1;
      pascal[i][i] = 1;
      for (int j = 1; j < i; j++) {
        pascal[i][j] = (int) (((long)pascal[i-1][j-1] + (long)pascal[i-1][j]) % MOD);
      }
    }
    return pascal;
  }


  static String trace(int[] a) {
    StringBuilder sb = new StringBuilder();
    for (int v : a) {
     if (sb.length() > 0) {
       sb.append(' ');
     }
      sb.append(v);
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    Scanner in = getInputScanner();
    int n = in.nextInt();
    int k = in.nextInt();
    String s = in.next();
    int ans = solve(s, k);
    System.out.println(ans);
    in.close();
  }

  static Scanner getInputScanner() {
    try {
      final String USERDIR = System.getProperty("user.dir");
      final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
      final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
      return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
    } catch (Exception e) {
      return new Scanner(System.in);
    }
  }
}
