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 Solution {
    static class NCR {
        private final long[] fact;
        private final long[] inv;
        private final long[] invfact;
        private final int MOD = 998244353;
        private final int n;

        public NCR(int n) {
            this.n = n;
            fact = new long[n];
            inv = new long[n];
            invfact = new long[n];
            factInverse();
        }

        public int nCr(int n, int r) {
            if (r > n) {
                return 0;
            }
            return (int) ((((fact[n] * invfact[r]) % MOD) * invfact[n - r]) % MOD);
        }

        private void factInverse() {
            fact[0] = inv[1] = fact[1] = invfact[0] = invfact[1] = 1;
            for (int i = 2; i < n; i++) {
                fact[i] = (fact[i - 1] * i) % MOD;
                inv[i] = MOD - (inv[MOD % i] * (MOD / i) % MOD);
                invfact[i] = (inv[i] * invfact[i - 1]) % MOD;
            }
        }
    }

    public static void main(String[] args) throws Exception {
        int tc = 1;
        for (int i = 0; i < tc; i++) {
            solve();
        }
        io.close();
    }

    static NCR ncr = new NCR(5005);

    private static void solve() throws Exception {
        int n = io.nextInt();
        int k = io.nextInt();
        String s = io.next();

        int oneCount = 0;
        for (char c : s.toCharArray()) if (c == '1') oneCount++;
        if (oneCount < k || k == 0) {
            io.println(1);
            return;
        }

        int res = solve2(s, k);

        int firstOneIdx = s.indexOf('1');
        int lastOneIdx = s.lastIndexOf('1');
        if (firstOneIdx == -1) {
            io.print(1);
        }
        if (lastOneIdx > firstOneIdx) {
            res -= solve2(s.substring(firstOneIdx + 1, lastOneIdx), k - 1);
            res += 998244353;
            res %= 998244353;
        }
        io.print(res);
    }

    static int solve2(String s, int k) {
        int i = 0;
        int j = -1;
        int count1 = 0;
        int output = 0;
        if (k == 0) return 1;
        while (true) {
            while (j < s.length() && count1 <= k) {
                if (j + 1 < s.length() && s.charAt(j + 1) == '1') {
                    count1++;
                }
                j++;
            }
            if (count1 - 1 == k) {
                output += ncr.nCr(j - 1 - i + 1, k);
                output %= 998244353;
            }
            while (count1 - 1 == k) {
                if (s.charAt(i) == '1') {
                    count1--;
                }
                i++;
            }
            if (j == s.length()) break;
        }
        if (count1 == k) {
            output += ncr.nCr(j - i, k);
            output %= 998244353;
        }

        return output;
    }


    static void sort(int[] a) {
        ArrayList<Integer> l = new ArrayList<>(a.length);
        for (int i : a) l.add(i);
        Collections.sort(l);
        for (int i = 0; i < a.length; i++) a[i] = l.get(i);
    }

    //-----------PrintWriter for faster output---------------------------------
    public static FastIO io = new FastIO();

    //-----------MyScanner class for faster input----------
    static class FastIO extends PrintWriter {
        private InputStream stream;
        private byte[] buf = new byte[1 << 16];
        private int curChar, numChars;

        // standard input
        public FastIO() {
            this(System.in, System.out);
        }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public String nextLine() {
            int c;
            do {
                c = nextByte();
            } while (c < '\n');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > '\n');
            return res.toString();
        }

        public int nextInt() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public long nextLong() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }


        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
    //--------------------------------------------------------
}