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

''' D. Shuffle
https://codeforces.com/contest/1622/problem/D
'''
 
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline  # decode().strip() if str
output = sys.stdout.write
 
DEBUG = os.environ.get('debug') is not None
 
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search
 
def debug(*args):
    if not DEBUG: return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search(r"\((.*)\)", s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for var, val in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f'{prefix}{", ".join(var_and_vals)}')
 
 
INF = float('inf')
 
# -----------------------------------------

def batch_nCk(N, p):
    ''' precompute for binomial coefficient up to C(N, N) % p
    C(N, k) mod p = fact[n] * inv_fact[k] * inv_fact[n-k]
    '''
    fact = [1]*(N+1)  # n! % p
    for i in range(1, N+1):
        fact[i] = (i * fact[i-1]) % p
 
    inv_fact = [1]*(N+1)  # (1 / n!) % p
    for i in range(1, N+1):
        inv_fact[i] = pow(fact[i], p-2, p)
    
    return fact, inv_fact
 
 
MOD = 998244353
MAX = 5005
FACT, INV_FACT = batch_nCk(MAX, MOD)


# say S becomes S' after shuffling a substring
# then S' must have a minimal mid-segment that's different from S
# formally there exists i, j s.t. S[:i] == S'[:i], S[j+1:] == S'[j+1:], S[i] != S'[i], S[j] != S'[j]
 
# different resultant S' are uniquely identified by their i, j
# a segment i..j is valid (can be substring of a substring with exactly K 1s) if 
# * S has >= K 1s
# * S[i..j] has <= K 1s

def solve_N2(N, K, S):
    if K == 0 or sum(S) < K: return 1
 
    res = 1
    for i in range(N):
        cnt = 0
        for j in range(i, N):
            if S[j] == 1: cnt += 1
            if cnt > K: break
            mid_cnt = cnt - (S[i] == 0) - (S[j] == 0)
            if 0 <= mid_cnt <= j - i - 1:
                res += FACT[j - i - 1] * INV_FACT[mid_cnt] * INV_FACT[j - i - 1 - mid_cnt]
                res %= MOD
 
    return res
 

# let j be the first idx where S' differs from S
# formally S[:j] == S'[:j], S[j] != S'[j]
# then different resultant S' are uniquely identified by their j
# a segment i..j is valid if it has <= K 1s

def solve_N(N, K, S):
    if K == 0 or sum(S) < K: return 1

    res = 1
    cnt = i = 0
    for j, n in enumerate(S):
        cnt += n
        while cnt > K: 
            cnt -= S[i]
            i += 1

        one, zero = cnt, j - i + 1 - cnt
        if n == 0: one -= 1
        if n == 1: zero -= 1

        if one < 0 or zero < 0: continue
        res += FACT[one+zero] * INV_FACT[one] * INV_FACT[zero]
        res %= MOD

    return res

solve = solve_N

def main():
    N, K = list(map(int, input().split()))
    S = list(map(int, list(input().decode().strip())))
    out = solve(N, K, S)
    output(f'{out}\n')
 
 
if __name__ == '__main__':
    main()
 
