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

import java.io.*;
import java.util.*;

public class Main {
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		byte[] bb = new byte[1 << 15]; int i, n;
		byte getc() {
			if (i == n) {
				i = n = 0;
				try { n = in.read(bb); } catch (IOException e) {}
			}
			return i < n ? bb[i++] : 0;
		}
		int nextInt() {
			byte c = 0; while (c <= ' ') c = getc();
			int a = 0; while (c > ' ') { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
		long nextLong() {
			byte c = 0; while (c <= ' ') c = getc();
			long a = 0; while (c > ' ') { a = a * 10L + c - '0'; c = getc(); }
			return a;
		}
	}
	
	private static class Interval {
		int left;
		int right;
		Interval(int left, int right) {
			this.left = left;
			this.right = right;
		}
		
		public Interval	intersect(Interval b) {
			return new Interval(b.left, this.right);
		}
	}

	private static long pow(long a, long b, long c) {
		if (b == 0)return 1;
		if (b % 2 == 0) {
			long ans = pow(a, b/2, c);
			return ans * ans % c;
		} else {
			return pow(a, b-1, c) * a % c;
 		}
	}
	
	public static void main(String[] args) throws Exception {
		//Scanner in = new Scanner(System.in);
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));		
		
		long REM = 998244353L;
		long[] fact = new long[6000];
		long[] inv_fact = new long[6000];
		
		fact[0] = 1;
		inv_fact[0] = pow(1, REM-2, REM);
		for (int i=1; i<fact.length; i++) {
			fact[i] = (fact[i-1] * i) % REM;
			inv_fact[i] = inv_fact[i-1] * pow(i, REM-2, REM) % REM;
		}
		
		String[] line = in.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int K = Integer.parseInt(line[1]);
		
		String S = in.readLine();
		
		int left = 0;
		int right = 0;
		
		int count = 0;
		while (right < N) {
			if (S.charAt(right) == '1') count++;
			if (count > K) break;
			right++;
			//out.write(right + " " + count + "\n");
		}
		right--;
		
		
		List<Interval> intervals = new ArrayList<>();
		intervals.add(new Interval(left, right));
		//out.write(left + " " + right + "\n");
		
		int counter = 1;
		while (right < N - 1) {
			while (S.charAt(left) == '0') left++;
			left++;
			
			right++; //1
			right++; //0
			while (right < N && S.charAt(right) == '0') right++;
			right--;
			
			//out.write(left + " " + right + "\n");
			
			intervals.add(new Interval(left, right));
			counter++;
			//if (counter == 3) break;
		}
		
		
		int total_count = 0;
		for (int idx=0; idx<S.length(); idx++) {
			if (S.charAt(idx) == '1') {
				total_count++;
			}
		}
		long ans = 0;
		if (K == 0 || total_count < K) {
			intervals = new ArrayList<>();
			ans = 1;
		}
		
		
		for (int i=0; i<intervals.size(); i++) {
			Interval lr = intervals.get(i);
			//out.write(lr.left + " " + lr.right + "\n");
			//out.write(fact[lr.right-lr.left+1] + "\n");
			//out.write(inv_fact[K] + "\n");
			//out.write(inv_fact[lr.right-lr.left+1-K] + "\n");
			long res = fact[lr.right-lr.left+1]*inv_fact[K]%REM*inv_fact[lr.right-lr.left+1-K]%REM;
			ans = (ans + res) % REM;
			//out.write("ans = " + ans + "\n");
		}
		
		for (int i=0; i<intervals.size()-1; i++) {
			Interval lr = intervals.get(i).intersect(intervals.get(i+1));
			//out.write("HERE\n");
			//out.write(lr.left + " " + lr.right + "\n");
			long res = fact[lr.right-lr.left+1]*inv_fact[K-1]%REM*inv_fact[(lr.right-lr.left+1)-(K-1)]%REM;
			ans = (ans + REM - res) % REM;
		}
		
		out.write(ans + "\n");
		
		in.close();
		out.close();
	}

}
