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 \le n \le 5000$; $0 \le k \le 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.

Difficulty: HARD
Tags: Combinatorics

Amortized analysis

Mathematics
Skill types: Amortized analysis

Starter code:

Solutions:
M = 998244353
MAXNUM = 100000
factor = [1] * (MAXNUM + 2)
factor[-1] = 0
storecomb = {}
for i in range(1, MAXNUM + 1):
	factor[i] = factor[i - 1] * i % M

def fastfrac(a, b):
	numb = pow(b, M - 2, M)
	return a % M * (numb % M) % M

def comb(n, k):
	if k < 0:
		return 0
	if n < k:
		return 0
	if n == k:
		return 1
	if (n, k) in storecomb:
		return storecomb[n, k]
	num1 = factor[n]
	num2 = factor[k]
	num3 = factor[n - k]
	num = num2 * num3 % M
	output = fastfrac(num1, num)
	storecomb[n, k] = output
	return output

def main(t):
	(n, k) = map(int, input().split())
	s = input()
	if k == 0:
		print(1)
		return
	count = 0
	for i in range(n):
		if s[i] == '1':
			count += 1
	if count < k:
		print(1)
		return
	ones = [-1]
	ans = 1
	for i in range(n):
		if s[i] == '1':
			ones.append(i)
			if len(ones) < k + 1:
				front = -1
			else:
				front = ones[-k - 1]
			num = min(k, len(ones) - 1)
			ans += comb(i - front - 1, num)
		else:
			if len(ones) == 1:
				continue
			if len(ones) < k + 1:
				front = -1
			else:
				front = ones[-k - 1]
			num = min(k, len(ones) - 1)
			ans += comb(i - front - 1, num - 1)
		ans = ans % M
	print(ans % M)
T = 1
t = 1
while t <= T:
	main(t)
	t += 1


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
fact = [1]
for i in range(1, 10005):
	fact.append(fact[-1] * i % mod1)
inv = [pow(fact[-1], mod1 - 2, mod1)]
for i in range(10004, 0, -1):
	inv.append(inv[-1] * i % mod1)
inv.reverse()
(n, k) = il()
s = list(ip())
if k == 0:
	print(1)
	exit(0)
s = ['#'] + s
pre = [0 for i in range(n + 2)]
suf = [0 for i in range(n + 2)]
ch = [[0, 0] for i in range(n + 1)]
c = 0
for i in range(1, n + 1):
	ch[i] = ch[i - 1].copy()
	t = 0
	if s[i] == '1':
		t = 1
	ch[i][t] += 1
	if s[i] == '0':
		c += 1
	else:
		pre[i] = c
		c = 0
if k == 0 or ch[n][1] - ch[0][1] < k:
	print(1)
	exit(0)
c = 0
for i in range(n, 0, -1):
	if s[i] == '0':
		c += 1
	else:
		suf[i] = c
		c = 0
ans = 0
for i in range(1, n + 1):
	if s[i] == '0':
		continue
	j = i
	c = 0
	while j <= n and c < k:
		if s[j] == '1':
			c += 1
		j += 1
	if c < k:
		break
	z = pre[i] + suf[j - 1] + ch[j - 1][0] - ch[i - 1][0]
	ans += fact[z + k] * inv[k] * inv[z] % mod1
	ans %= mod1
ans1 = 0
for i in range(1, n + 1):
	if s[i] == '0':
		continue
	j = i
	c = 0
	while j <= n and c <= k:
		if s[j] == '1':
			c += 1
		j += 1
	if c <= k:
		break
	z = ch[j - 1][0] - ch[i - 1][0]
	ans1 += fact[z + k - 1] * inv[k - 1] * inv[z] % mod1
	ans1 %= mod1
ans = (ans + mod1 - ans1) % mod1
print(ans)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

def bootstrap(f, stack=[]):

	def fun(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return fun

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), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
N = 100001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans % p
p = 998244353
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
t = 1
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	b = []
	pre = [0]
	for j in s:
		b.append(int(j))
		pre.append(pre[-1] + b[-1])
	ans = 1
	if k > 0 and k <= pre[-1]:
		for i in range(n):
			j = i - 1
			o = 0
			z = 0
			if b[i]:
				o = 1
			else:
				z = 1
			while j >= 0:
				if pre[i + 1] - pre[j] > k:
					j += 1
					break
				else:
					if b[j]:
						o += 1
					else:
						z += 1
					j += -1
			if j == -1:
				j = 0
			if z >= 1 and o >= 1:
				if b[i]:
					z -= 1
				else:
					o -= 1
				ans = (ans + Binomial(z + o, z, p)) % p
	print(ans)


from functools import lru_cache

@lru_cache(None)
def fac(x):
	if x == 0:
		return 1
	else:
		return x * fac(x - 1) % MOD

@lru_cache(None)
def ifac(x):
	return pow(fac(x), MOD - 2, MOD)

def C(x, y):
	if x < y:
		return 0
	return fac(x) * ifac(y) * ifac(x - y) % MOD
MOD = 998244353
for i in range(5000):
	fac(i)
(n, k) = map(int, input().split())
s = input()
if k == 0:
	print(1)
else:
	left = 0
	cnt = 0
	res = 0
	start = False
	flag = False
	for i in range(len(s)):
		if s[i] == '1':
			cnt += 1
		while cnt > k:
			if s[left] == '1':
				cnt -= 1
			left += 1
		if cnt == k:
			if not start:
				res += C(i - left + 1, k)
			elif s[i] == '1':
				res += C(i - left, k)
			else:
				res += C(i - left, k - 1)
			start = True
			flag = True
			res %= MOD
	if res == 0 and (not flag):
		res = 1
	print(res)


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
fact = [1] * 5005
for i in range(1, 5005):
	fact[i] = fact[i - 1] * i % mod2
(n, k) = M()
s = S()
if k == 0 or k > s.count('1'):
	print(1)
else:
	ans = 0
	a = []
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	for i in range(len(a) - k + 1):
		l = a[i] - 1
		r = a[i + k - 1] + 1
		p = r - 1
		while l >= 0 and s[l] == '0':
			l -= 1
		while r < n and s[r] == '0':
			r += 1
		l += 1
		r -= 1
		t = r - l + 1
		f1 = fact[t] * pow(fact[t - k], mod2 - 2, mod2) * pow(fact[k], mod2 - 2, mod2) % mod2
		ans = (ans + f1) % mod2
		t1 = t - (r - p + 1)
		k1 = k - 1
		if i == 0:
			continue
		f2 = fact[t1] * pow(fact[t1 - k1], mod2 - 2, mod2) * pow(fact[k1], mod2 - 2, mod2) % mod2
		ans = (ans - f2) % mod2
	print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
S = list(input().rstrip())
S = [int(s) for s in S]
mod = 998244353
from time import time
it = time()
cons = 0
prof = []
for s in S:
	if s == 0:
		cons += 1
	else:
		prof.append(cons)
		cons = 0
prof.append(cons)
_inv_t = {}
_inv_t[1] = 1
_inv_t[0] = 0

def inv(x, mod):
	x %= mod
	if x not in _inv_t:
		_inv_t[x] = inv(mod % x, mod) * (mod - mod // x) % mod
	return _inv_t[x]
for x in range(2, N + 10):
	_inv_t[x] = inv(mod % x, mod) * (mod - mod // x) % mod
comb = [[1, 0], [1, 1, 0]]
for n in range(2, N + 3):
	now = 1
	arr = [1]
	for i in range(1, n + 1):
		arr.append((comb[-1][i - 1] + comb[-1][i]) % mod)
	arr.append(0)
	comb.append(arr)
import sys
if K == 0:
	print(1)
	sys.exit()
if K > S.count(1):
	print(1)
	sys.exit()
ans = 0
fac = -1
for k in range(K, max(-1, K - 2), -1):
	fac *= -1
	n = sum(prof[K - k:K + 1]) + k
	for i in range(K + 1, len(prof) - (K - k) + 1):
		ans += comb[n][k] * fac
		ans %= mod
		if i < len(prof):
			n += prof[i]
			n -= prof[i - k - 1]
print(ans)


from sys import stdin
input = stdin.readline
mod = 998244353

def add(a, b):
	return (a % mod + b % mod) % mod

def sub(a, b):
	return (a - b + mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def div(a, b):
	return mul(a, pow(b, mod - 2, mod))
size = 5001
(fact, facti) = ([1], [1])
for i in range(1, size):
	fact.append(mul(fact[-1], i))
	facti.append(pow(fact[-1], mod - 2, mod))

def get(n, x, y):
	ans = mul(fact[n], mul(facti[x], facti[y]))
	return ans

def answer():
	(ans, prevupper, i) = (1, [-1], 0)
	for i in range(n):
		(count, upper) = (0, -1)
		for j in range(i, n):
			if a[j] == '1':
				count += 1
			if count == k + 1:
				upper = j - 1
				break
		if count == k:
			upper = n - 1
		if upper == -1:
			break
		ans = add(ans, get(upper - i + 1, k, upper - i + 1 - k))
		if prevupper[-1] > i:
			(x, y) = (0, 0)
			for j in range(i, prevupper[-1] + 1):
				x += a[j] == '1'
				y += a[j] == '0'
			ans = sub(ans, get(prevupper[-1] - i + 1, x, y))
		else:
			ans = sub(ans, 1)
		prevupper.append(upper)
	return ans
for T in range(1):
	(n, k) = map(int, input().split())
	a = input().strip()
	print(answer())


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
mod = 998244353
s = list(input().rstrip())
l = n + 5
fact = [1] * (l + 1)
for i in range(1, l + 1):
	fact[i] = i * fact[i - 1] % mod
inv = [1] * (l + 1)
inv[l] = pow(fact[l], mod - 2, mod)
for i in range(l - 1, -1, -1):
	inv[i] = (i + 1) * inv[i + 1] % mod

def comb(n, r):
	return fact[n] * inv[r] % mod * inv[n - r] % mod if n >= r >= 0 else 0
x = [-1]
for i in range(n):
	if s[i] == '1':
		x.append(i)
x.append(n)
l = len(x) - 1
ans = 1
for i in range(1, len(x) - 1):
	xi = x[i]
	l = i - 1 if i < k else x[i - k] + 1
	for j in range(l, x[i + 1]):
		if xi == j:
			continue
		c = min(i - 1, k - 1)
		m = j - 1 - x[max(0, i - k)]
		ans += comb(m, c)
		ans %= mod
if len(x) - 2 < k:
	ans = 1
print(ans)


import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
mod = 998244353
facs = [1]
ifacs = [1]
for i in range(1, 5001):
	facs.append(facs[-1] * i % mod)
	ifacs.append(ifacs[-1] * pow(i, mod - 2, mod) % mod)

def binom(n, m):
	return facs[n] * ifacs[m] * ifacs[n - m] % mod
(n, k) = I()
s = input()
ones = []
for i in range(n):
	if s[i] == '1':
		ones.append(i)
tot = 1
if len(ones) < k:
	print(1)
	exit()
for i in range(len(ones)):
	if i == 0:
		start = 0
	else:
		start = ones[i - 1] + 1
	if i + k >= len(ones):
		end = n - 1
	else:
		end = ones[i + k] - 1
	tot += binom(end - start + 1, min(k, len(ones) - i))
	tot -= binom(end - ones[i], min(k, len(ones) - i) - 1)
	tot %= mod
print(tot)


from sys import stdin
from itertools import accumulate
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 998244353

def make_nCr_mod(max_n=2 * 10 ** 5):
	max_n = min(max_n, mod - 1)
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res
	return nCr_mod
(n, k) = rns()
a = list(map(int, rs()))
acc = list(accumulate(a))

def solve():
	j = 0
	ans = 1
	choose = make_nCr_mod()
	first = True
	for i in range(n):
		if j == n:
			break
		while j < n and acc[j] - acc[i] + a[i] <= k:
			if acc[j] - acc[i] + a[i] == k:
				add = 0
				if not first:
					if a[j] == 0:
						add = choose(j - i, k - 1)
					elif j - i + 1 > k:
						add = choose(j - i, k)
				else:
					if a[j] == 0:
						add = choose(j - i + 1, k - 1) - 1
					elif j - i + 1 > k:
						add = choose(j - i + 1, k) - 1
					first = False
				ans += add
				ans %= mod
			j += 1
	return ans
print(solve())


(n, k) = map(int, input().split())
mod = 998244353
s = input()
facs = [1]
ifacs = [1]
for i in range(1, n + 1):
	facs.append(facs[-1] * i % mod)
	ifacs.append(ifacs[-1] * pow(i, mod - 2, mod) % mod)
cc = sum([1 for c in s if c == '1'])
ans = 1
for i in range(n):
	(c0, c1) = (0, 0)
	for j in range(i, n):
		if s[j] == '1':
			c1 += 1
		else:
			c0 += 1
		if c1 > k or cc < k:
			continue
		(nc0, nc1) = (c0, c1)
		if s[i] == '1':
			nc0 -= 1
		else:
			nc1 -= 1
		if s[j] == '1':
			nc0 -= 1
		else:
			nc1 -= 1
		if nc0 < 0 or nc1 < 0:
			continue
		assert nc0 + nc1 + 2 == j - i + 1
		ans += facs[nc0 + nc1] * ifacs[nc1] * ifacs[nc0]
		ans %= mod
print(ans)


import sys
int1 = lambda x: int(x) - 1
pDB = lambda *x: print(*x, end='\n', file=sys.stderr)
p2D = lambda x: print(*x, sep='\n', end='\n\n', file=sys.stderr)

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

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

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

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
inf = 4294967295
md = 998244353

def nCr(com_n, com_r):
	if com_r < 0:
		return 0
	if com_n < com_r:
		return 0
	return fac[com_n] * ifac[com_r] % md * ifac[com_n - com_r] % md
n_max = 5005
fac = [1]
for i in range(1, n_max + 1):
	fac.append(fac[-1] * i % md)
ifac = [1] * (n_max + 1)
ifac[n_max] = pow(fac[n_max], md - 2, md)
for i in range(n_max - 1, 1, -1):
	ifac[i] = ifac[i + 1] * (i + 1) % md
(n, k) = LI()
aa = list(map(int, SI()))
if k == 0 or aa.count(1) < k:
	print(1)
	exit()
aa.append(1)
s = 0
r = -1
while r + 1 <= n and s <= k:
	r += 1
	s += aa[r]
f = 0
while f < n and aa[f] == 0:
	f += 1
ans = nCr(r, s - 1) - nCr(r - f - 1, s - 2) + 1
ans %= md
for (i, a) in enumerate(aa):
	if a:
		l = i + 1
		f = l
		while f < n and aa[f] == 0:
			f += 1
		s -= 1
		while r + 1 <= n and s <= k:
			r += 1
			s += aa[r]
		if s == 1:
			break
		ans += nCr(r - l, s - 1) - nCr(r - f - 1, s - 2)
		ans %= md
print(ans)


O = input
(E, F, C, G) = (998244353, [1], [1], range)
for A in G(1, 5001):
	F += [F[-1] * A]
	C += [C[-1] * pow(A, -1, E) % E]
(I, D) = map(int, O().split())
(J, N) = (lambda n, m: F[n] * C[m] * C[n - m], O())
(B, K) = ([A for A in G(I) if N[A] > '0'], 1)
H = len(B)
B += [I] * D + [-1]
for A in G(H):
	L = B[A + D] - 1
	M = min(D, H - A)
	K += J(L - B[A - 1], M) - J(L - B[A], M - 1)
print([K % E, 1][H < D])


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

def solve(t):
	md = 1000000007
	md2 = 998244353
	mx = 1000000000
	mx2 = 1e+18
	(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))
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), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import heapq
from bisect import bisect_left
from collections import Counter, deque, defaultdict
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(300005)
LOGN = 20
INF = 10 ** 9 + 5
MOD = 998244353

class nCk:

	def __init__(self, maxn, mod):
		self.mod = mod
		self.fact = fact = [1 for _ in range(maxn + 1)]
		self.temp = temp = [1 for _ in range(maxn + 1)]
		self.invs = invs = [1 for _ in range(maxn + 1)]
		for i in range(2, maxn + 1):
			fact[i] = fact[i - 1] * i % mod
			temp[i] = -temp[mod % i] * (mod // i) % mod
			invs[i] = invs[i - 1] * temp[i] % mod

	def get(self, n, k):
		if not 0 <= k <= n:
			return 0
		return self.fact[n] * self.invs[k] % self.mod * self.invs[n - k] % self.mod

def solve():
	(N, K) = map(int, input().split())
	S = input()
	if S.count('1') < K or K == 0:
		print(1)
		return
	nck = nCk(5001, MOD)
	ans = left = 0
	cur_ones = 0
	for right in range(N):
		cur_ones += int(S[right])
		while cur_ones > K:
			cur_ones -= int(S[left])
			left += 1
		if S[right] == '1' and right - left >= cur_ones:
			ans += nck.get(right - left, cur_ones)
		if S[right] != '1' and right - left >= cur_ones - 1 >= 0:
			ans += nck.get(right - left, cur_ones - 1)
		ans %= MOD
	print((ans + 1) % MOD)
solve()


(M, F, f, r) = (998244353, [1], [1], range)
for i in r(1, 5001):
	F.append(F[-1] * i % M)
	f.append(f[-1] * pow(i, -1, M) % M)
(n, k) = map(int, input().split())
(b, s) = (lambda n, m: F[n] * f[m] * f[n - m] % M, input())
(o, T) = ([i for i in range(n) if s[i] > '0'], 1)
l = len(o)
for i in r(k):
	o.append(n)
o.append(-1)
if l < k:
	print(1)
	exit()
for i in r(l):
	e = o[i + k] - 1
	x = min(k, l - i)
	T = (T + b(e - o[i - 1], x) - b(e - o[i], x - 1)) % M
print(T)


import sys
import io, os
input = sys.stdin.readline
mod = 998244353
N = 5001
fac = [1] * (N + 1)
finv = [1] * (N + 1)
for i in range(N):
	fac[i + 1] = fac[i] * (i + 1) % mod
finv[-1] = pow(fac[-1], mod - 2, mod)
for i in reversed(range(N)):
	finv[i] = finv[i + 1] * (i + 1) % mod

def cmb1(n, r):
	return fac[n] * finv[r] * finv[n - r] % mod
(n, k) = map(int, input().split())
s = str(input().rstrip())
C = [0] * (n + 1)
for (i, c) in enumerate(s):
	if c == '1':
		C[i + 1] = C[i] + 1
	else:
		C[i + 1] = C[i]
if C[n] < k:
	print(1)
	exit()
ans = 1
for i in range(n):
	if s[i] == '0':
		flag = True
	else:
		flag = False
	for j in range(i + 1, n):
		cnt1 = C[j + 1] - C[i]
		cnt = j - i + 1
		if cnt1 > k:
			break
		cnt -= 2
		if flag:
			cnt1 -= 1
		if s[j] == '0':
			cnt1 -= 1
		if cnt1 <= cnt and cnt1 >= 0 and (cnt >= 0):
			ans += cmb1(cnt, cnt1)
			ans %= mod
print(ans)


import os
import sys
from io import BytesIO, IOBase
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), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
f = [1] * 100001
fi = [1] * 100001
a = 1
m = 998244353
for i in range(1, 100001):
	a *= i
	a %= m
	f[i] = a
b = pow(f[100000], m - 2, m)
fi[100000] = b
for i in range(99999, -1, -1):
	fi[i] = b * (i + 1) % m
	b = fi[i]
(n, k) = map(int, input().split())
s = input()
if k == 0:
	print(1)
elif s.count('1') < k:
	print(1)
elif s.count('1') == k:
	print(f[n] * fi[k] * fi[n - k] % m)
else:
	c = 0
	for i in range(n):
		if s[i] == '1':
			c += 1
		if c > k:
			c -= 1
			break
	ans = f[i] * fi[k] * fi[i - k]
	ans %= m
	a = 0
	for j in range(i, n):
		if s[j] == '1':
			c += 1
		while c > k:
			if s[a] == '1':
				c -= 1
			a += 1
		ans += f[j - a + 1] * fi[c] * fi[j - a + 1 - c] + m
		if s[j] == '1':
			ans -= f[j - a] * fi[c - 1] * fi[j - a - c + 1]
		else:
			ans -= f[j - a] * fi[c] * fi[j - a - c]
		ans %= m
	print(ans)


import sys

def solve():
	MOD = 998244353
	inp = sys.stdin.readline
	(n, k) = map(int, inp().split())
	s = list(map(int, inp().strip()))
	if sum(s) < k:
		print(1)
		return
	C = [None] * n
	C[0] = [1]
	for i in range(1, n):
		a = [None] * (i + 1)
		C[i] = a
		b = C[i - 1]
		a[0] = 1
		a[i] = 1
		for j in range(1, i):
			a[j] = (b[j - 1] + b[j]) % MOD
	r = 1
	for i in range(n):
		c = [0, 0]
		a = s[i]
		c[a] += 1
		for j in range(i + 1, n):
			b = s[j]
			c[b] += 1
			if c[1] > k:
				break
			if c[b ^ 1] > 0:
				c[b ^ 1] -= 1
				if c[a ^ 1] > 0:
					c[a ^ 1] -= 1
					r = (r + C[j - i - 1][c[0]]) % MOD
					c[a ^ 1] += 1
				c[b ^ 1] += 1
	print(r)

def main():
	solve()
main()


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
sys.setrecursionlimit(3 * 10 ** 5)
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
fact = [0] * 6010
inv = [0] * 6010
fact[0] = 1
fact[1] = 1
inv[0] = 1
inv[1] = 1
for i in range(2, 6002):
	fact[i] = fact[i - 1] * i % mod1
	inv[i] = pow(fact[i], mod1 - 2, mod1)

def ncr(n, r):
	if r == 0 or n == 0:
		return 1
	ans = fact[n] * inv[r] * inv[n - r]
	ans %= mod1
	return ans

def hnbhai(tc):
	(n, k) = sd()
	s = 's' + sa()
	prefix = [0] * (n + 1)
	suffix = [0] * (n + 1)
	dp = [[0, 0] for i in range(n + 1)]
	tot = 0
	pos = []
	for i in range(1, n + 1):
		dp[i] = dp[i - 1].copy()
		dp[i][int(s[i])] += 1
		if int(s[i]) == 0:
			tot += 1
		else:
			pos.append(i)
			prefix[i] = tot
			tot = 0
	if k == 0 or dp[n][1] - dp[0][1] < k:
		print(1)
		return
	temp = 0
	for i in range(n, 0, -1):
		if int(s[i]) == 0:
			temp += 1
		else:
			suffix[i] = temp
			temp = 0
	tot = 0
	ans = 0
	(l, r) = (100000, -1)
	for i in range(len(pos)):
		if i + k == len(pos):
			temp = prefix[pos[i]] + n - pos[i] + 1
			ans += ncr(temp, k)
			ans %= mod1
			break
		temp = prefix[pos[i]] + pos[i + k] - pos[i]
		ans += ncr(temp, k)
		ans -= ncr(temp - 1 - prefix[pos[i]], k - 1)
		ans %= mod1
	print(ans)
	return
for _ in range(1):
	hnbhai(_ + 1)


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
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('\\((.*)\\)', 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):
	fact = [1] * (N + 1)
	for i in range(1, N + 1):
		fact[i] = i * fact[i - 1] % p
	inv_fact = [1] * (N + 1)
	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)

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

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')
main()


import sys
input = sys.stdin.readline
mod = 998244353

def power(num, ex):
	(pw, res) = (num, 1)
	while ex:
		if ex & 1:
			res = res * pw
		pw = pw * pw
		ex >>= 1
	return res

def power_with_modulo(num, ex):
	(pw, res) = (num % mod, 1)
	while ex:
		if ex & 1:
			res = res * pw % mod
		pw = pw * pw % mod
		ex >>= 1
	return res
(n, k) = map(int, input().split())
s = str(input())
ans = 1
prefix_sum = [0 for i in range(n)]
fac = [1 for i in range(n + 1)]
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
prefix_sum[0] = 1 if s[0] == '1' else 0
for i in range(1, n):
	prefix_sum[i] = prefix_sum[i - 1] + int(s[i] == '1')
if prefix_sum[n - 1] < k:
	print(1)
	exit()
C = [[0 for i in range(n + 1)] for i in range(n + 1)]
C[0][0] = 1
for i in range(1, n + 1):
	C[i][0] = 1
	for j in range(1, i + 1):
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod
for i in range(n):
	for j in range(i + 1, n):
		cnt = j - i + 1
		cnt1 = prefix_sum[j] - (prefix_sum[i - 1] if i >= 1 else 0)
		if cnt1 > k:
			continue
		cnt -= 2
		if s[i] == '0':
			cnt1 -= 1
		if s[j] == '0':
			cnt1 -= 1
		if cnt1 >= 0 and cnt >= cnt1:
			ans = (ans + C[cnt][cnt1]) % mod
print(ans)


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)


from __future__ import division, print_function
import math
import sys
import os
from io import BytesIO, IOBase
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), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

def inps():
	return input().strip()

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
N = 10000
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p
mod = 998244353
InverseofNumber(mod)
InverseofFactorial(mod)
factorial(mod)
F = fact
I = factorialNumInverse
(n, k) = invr()
l = insr()
arr = [-1]
for i in range(n):
	if l[i] == '1':
		arr.append(i)
arr.append(n)
if k == 0 or k > len(arr) - 2:
	print(1)
else:
	v = len(arr)
	ans = 0
	for i in range(v - k - 1):
		(l, r) = (arr[i], arr[i + k + 1])
		d = r - l - 1
		ans += F[d] * I[k] * I[d - k]
		ans = ans % mod
		if i > 0:
			e = arr[i + k] - l - 1
			ans -= F[e] * I[k - 1] * I[e - k + 1]
			ans = ans % mod
	print(ans)


from sys import stdin, stdout
N = 998244353

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m=N):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
fact = [1]
invfact = [1]
for i in range(1, 5001):
	fact.append(fact[-1] * i % N)
	invfact.append(invfact[-1] * modinv(i) % N)
(n, k) = [int(x) for x in stdin.readline().split()]
s = stdin.readline().strip()
locations = []
for i in range(n):
	if s[i] == '1':
		locations.append(i)
if k == 0 or len(locations) < k:
	stdout.write('1\n')
else:
	answer = 0
	for i in range(len(locations) - k + 1):
		if i == 0:
			lower = 0
		else:
			lower = locations[i - 1] + 1
		if i == len(locations) - k:
			upper = n - 1
		else:
			upper = locations[i + k] - 1
		answer = (answer + fact[upper - lower + 1] * invfact[k] * invfact[upper - lower + 1 - k]) % N
	for i in range(len(locations) - k):
		lower = locations[i] + 1
		upper = locations[i + k] - 1
		answer = (answer - fact[upper - lower + 1] * invfact[k - 1] * invfact[upper - lower + 1 - k + 1]) % N
	stdout.write(str(answer) + '\n')


import sys
from sys import stdin
from collections import deque

def modfac(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)

def nCr(n, r):
	return fac[n] * inv[n - r] * inv[r] % mod
mod = 998244353
(fac, inv) = modfac(10000, mod)
tt = 1
ANS = []
for loop in range(tt):
	(n, k) = map(int, stdin.readline().split())
	s = list(stdin.readline()[:-1])
	ssum = 0
	for i in s:
		ssum += int(i)
	if ssum < k or k == 0:
		print(1)
		sys.exit()
	ans = 1
	q = deque([])
	qsum = 0
	for i in range(n):
		q.append(int(s[i]))
		qsum += int(s[i])
		while len(q) > 0 and qsum > k:
			qsum -= q.popleft()
		zero = len(q) - qsum
		one = qsum
		if s[i] == '0':
			one -= 1
		else:
			zero -= 1
		if one < 0 or zero < 0:
			continue
		ans += nCr(one + zero, one)
		ans %= mod
	ANS.append(str(ans % mod))
print('\n'.join(ANS))


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
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), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=10 ** 18, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10001)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10000):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

class LazySegUpdate:

	def __init__(self, N):
		self.N = N
		n = 4 * N
		self.tree = [0] * n
		self.lazy = [0] * n

	def queryHelper(self, index, s, e, l, r):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return 0
		if s >= l and e <= r:
			return self.tree[index]
		mid = (s + e) // 2
		return max(self.queryHelper(2 * index, s, mid, l, r), self.queryHelper(2 * index + 1, mid + 1, e, l, r))

	def updateHelper(self, index, s, e, l, r, h):
		if self.lazy[index]:
			update = self.lazy[index]
			self.lazy[index] = 0
			self.tree[index] = max(self.tree[index], update)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], update)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], update)
		if s > e or s > r or e < l:
			return
		if s >= l and e <= r:
			self.tree[index] = max(self.tree[index], h)
			if s != e:
				self.lazy[2 * index] = max(self.lazy[2 * index], h)
				self.lazy[2 * index + 1] = max(self.lazy[2 * index + 1], h)
			return
		mid = (s + e) // 2
		self.updateHelper(2 * index, s, mid, l, r, h)
		self.updateHelper(2 * index + 1, mid + 1, e, l, r, h)
		self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])

	def query(self, l, r):
		return self.queryHelper(1, 0, self.N - 1, l, r - 1)

	def update(self, l, r, h):
		self.updateHelper(1, 0, self.N - 1, l, r - 1, h)

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
tt = 1
for _ in range(tt):
	(n, k) = map(int, input().split())
	s = input()
	j = 0
	ans = 0
	c = Combination(omod)
	one = 0
	if s.count('1') < k:
		print(1)
		continue
	prev = 1
	for i in range(n):
		if one == k:
			one -= s[i] == '1'
			continue
		j = max(j, i)
		while j < n and one + int(s[j]) <= k:
			if s[j] == '1':
				prev = j
				one += 1
			j += 1
		if j == n and one < k:
			break
		l = j - i
		count = c.ncr(l, k)
		if i:
			count -= c.ncr(prev - i, k - 1)
		ans += count
		ans %= omod
		one -= s[i] == '1'
	print(ans)