human
Can you solve the below in PYTHON3?
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.
 Give me a Python code to print one integer — the number of different strings which can be obtained from s by performing the described operation at most once?
assistant
#Here is Python code to print one integer — the number of different strings which can be obtained from s by performing the described operation at most once.


from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

############################################################################
#                           ACTUAL CODE
############################################################################

def solve(t):
        
    md=1000000007
    md2=998244353
    mx=1000000000
    mx2=1e18

    n,k = map(int, input().split())
    s = input()
    f = []


    for i in range(n+1):
        f.append([1 for j in range(i+1)])
        for j in range(1, i):
            f[i][j]=(f[i-1][j]+f[i-1][j-1])%md2
    ans=1
    one = [0]
    for i in range(i):
        one.append(one[-1]+(s[i]=='1'))
        
    for i in range(n):
        for j in range(i+1, n):
            c = j-i+1
            c1 = one[j+1]-one[i]
            if c1 > k or one[n] < k:
                continue
            c -= 2
            c1 -= (s[i]=='0')
            c1 -= (s[j]=='0')
            if c1 <= c and c>=0 and c1>=0:
                ans =  (ans + (f[c][c1]))%md2
    return ans

def main():
    tc = 1
    for t in range(1, tc+1):
        print(solve(t))

#'''
############################################################################
#                         FAST-IO
#                         PyRIVAL
############################################################################

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b),...