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 collections
# import random
# import math
# import itertools
# import math
# import math
#import bisect
# from collections import defaultdict
# import itertools
# from sys import stdin, stdout
# import math
# import math
# import bisect
# import bisect
# import collections
# import itertools
# import math
# import collections
# import itertools
# import math
import bisect
import collections
import itertools
import math
import sys

# import operator
# from decimal import Decimal

# sys.setrecursionlimit(10**6)





p2D = lambda x: print(*x, sep="\n")


def II(): return int(sys.stdin.buffer.readline())


def MI(): return map(int, sys.stdin.buffer.readline().split())


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def BI(): return sys.stdin.buffer.readline().rstrip()


def SI(): return sys.stdin.buffer.readline().rstrip().decode()


def li(): return [int(i) for i in input().split()]


def lli(rows): return [li() for _ in range(rows)]


def si(): return input()


def ii(): return int(input())


def ins(): return input().split()


mod = 998244353
fval = [1]
for i in range(1,5002):
    x = (fval[-1]*i)%mod
    fval.append(x)

ifac = [1]*(5002)
ifac[5000] = pow(fval[5000], -1, mod)
for i in range(5000-1, 1, -1): ifac[i] = ifac[i+1]*(i+1)%mod
# _________________ For taking Input from the Text Files __________________
# import os.path
#
# if (os.path.exists('input.txt')):
#     sys.stdin = open("input.txt", "r")
#     sys.stdout = open("output.txt", "w")
#     sys.stderr = open("error.txt", "w")

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1



def binary_search(n, a):
    l = len(a)
    low = 0
    high = l-1
    while high>=low:
        mid = (high+low)//2
        if a[mid] == n:
            return mid
        elif a[mid]>n:
            high = mid-1
        else:
            low = mid+1
    return -1

# is_prime = [True]*(10**6+1)
# def primeseive(n):
#     is_prime[0] = is_prime[1] = False
#     i = 2
#     while i*i<=n:
#         if is_prime[i] == True:
#             for j in range(i*i,n+1,i):
#                 is_prime[j] = False
#         i+=1

def solve():
    n, k = li()
    s = si()
    if k == 0:
        return 1
    d = {}
    c = 0
    ones = [0]*(n+1)
    for i in range(n):
        if s[i]=='1':
            c+=1
            d[c] = i+1
        ones[i+1] = c
    if k>ones[-1]:
        return 1
    d[0] = 0
    d[c+1] = n+1
    ans = 0
    #print(d)
    segments = []
    for i in range(k, c+1):
        left = d[i-k]
        right = d[i+1]-1
        ans += (((fval[right-left]* ifac[k])%mod)*ifac[right-left-k])%mod
        segments.append([left+1, right])
    #print(segments)
    l = len(segments)
    for i in range(l):
        for j in range(i+1,l):
            if segments[i][1] >= segments[j][0]:
                comleft = segments[j][0]
                comright = segments[i][1]
                tones = ones[comright] - ones[comleft-1]
                tzeros = (comright-comleft+1)-tones
                ans-= (((fval[comright-comleft+1]* ifac[tzeros])%mod)*ifac[tones])%mod
            else: break

    return ans+l-min(l,2)

def main():
    #primeseive(10**6)
    #print(is_prime)

    #for _ in range(ii()):
        #si()
        #print(solve(), flush=True)
    sys.stdout.write(str(solve()) + "\n")
    #print(solve())

    #     z += str(ans) + '\n'
    # print(len(ans), ' '.join(map(str, ans)), sep='\n')
    # stdout.write(z)


# for interactive problems
# print("? {} {}".format(l,m), flush=True)
# or print this after each print statement
# sys.stdout.flush()


if __name__ == "__main__":
    main()