D. Distinct Subsequences
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ethan has a binary string $$$s$$$ of length $$$n$$$. He wants to give Justin a subsequence of $$$s$$$ as a present for his birthday. To make the present special, he wants to make sure the length of the subsequence is exactly Justin's favorite number — $$$k$$$.

Compute the number of distinct presents Ethan could give to Justin. As this value may be large, compute the answer modulo $$$998244353$$$.

Note: in this problem 'distinct' refers to the value of the subsequence. If a potential present appears as a subsequence of $$$s$$$ in multiple locations it is counted exactly once.

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot10^5$$$) — the length of string $$$s$$$ and the length of the desired subsequence respectively.

The second line of input contains a binary string $$$s$$$ of length $$$n$$$.

Output

Output the number of distinct subsequences of $$$s$$$ of length $$$k$$$, modulo $$$998244353$$$.

Examples
Input
5 3
00110
Output
5
Input
12 8
000111000000
Output
12
Input
31 12
1110100111110110101111010100010
Output
3985