human
Write me a Python program to print one integer — the number of different strings which can be obtained from s by performing the described operation at most once given the following:
PYTHON3 solution for "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.":
assistant
#Here is Python program to print one integer — the number of different strings which can be obtained from s by performing the described operation at most once.
 def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 998244353 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
N,K=map(int,input().split())
if K==0:
  print(1)
  exit()
S=input()
if K>S.count("1"):
  print(1)
  exit()
if K==S.count("1"):
  print(cmb(N,K))
  exit()
if K==1:
  ans=0
  for i in range(N):
    if S[i]=="1":
      ans+=(S.count("0")-i)
      
      break
  for i in range(N-1,-1,-1):
    if S[i]=="1":
      ans+=(S.count("0")-(N-1-i))
      break
  print(ans+1)
  exit()
  
ans=0
A=list()
i=0
for i in range(N):
  if S[i]=="1":
    A.append(i)
for i in range(len(A)-K-1):
  ans+=cmb(A[i+K+1]-A[i]-1,K)
  ans-=cmb(A[i+K]-A[i]-1,K-1)
  ans%=mod
ans+=cmb(A[K],K)
ans+=cmb(N-A[-(K+1)]-1,K)
ans-=cmb(A[(len(A)-K-1)+K]-A[len(A)-K-1]-1,K-1)
print(ans%mod)