H-Olefin_2021牛客暑期多校训练营2

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given a single-chain olefin containing ${n}$ bonds.

Now there are ${k}$ molecules of hydrogen, which can undergo ${k}$ addition reactions with this olefin.

An addition reaction, in organic chemistry, is in its simplest terms an organic reaction where two or more molecules combine to form a larger one (the adduct).^[1]^[2]

Addition reactions are limited to chemical compounds that have multiple bonds, such as molecules with carbon–carbon double bonds (alkenes), or with triple bonds (alkynes), and compounds that have rings, which are also considered points of unsaturation. Molecules containing carbon—hetero double bonds like carbonyl (C=O) groups, or imine (C=N) groups, can undergo addition, as they too have double-bond character.

—— Wikipedia

For example, addition reactions on 1,3-Butadiene may happen in the following ways:

In this problem, we can describe an olefin with $\ n+1$ carbon atoms as a string $S\$ consisting of $\ n\$ $\text{0,1}$ s :

If the ${i}^{th}$ character is ${0}$ , it means that the ${i} ^{th}$ carbon and the ${(i+1)} ^{th}$ carbon are connected by a carbon-carbon single bond;

Otherwise, it means that the ${i}^{th}$ carbon and the ${(i+1)}^{th}$ carbon are connected by a carbon-carbon double bond.

And any possible addition reaction can be described as an operation as follows:

1. Select a continuous non-empty substring of the string $S_{l},S_{l+1},\cdots,S_r$ . Both ends of the substring ( $S_l,S_r$ ) must be ${1}$ , and no two adjacent characters are the same. In particular, the substring may only contain one character, and the character is ${1}$ .

2. Change ${0}$ to ${1}$ and ${1}$ to ${0}$ in this substring.

And this operation can be recorded as $(l,r)\$ .

After one operation, the resulting string will correspond to a new olefin. This new olefin is the product of this addition reaction, and the next addition reaction will proceed to this new olefin.

The addition reaction happens $k\$ times orderly, that is, $k\$ operations $op_1,op_2,\cdots,op_k$ are done in sequence.

Please calculate the number of possible operation sequences, modulo ${998244353}$ .

Two operation sequences $op,op'\$ are different if and only if there is an ${i}$ that ${1≤i≤k} ,op_i\ne op'_i\$

As olefins with two adjacent carbon-carbon double bonds may not exist stably, you can assume that there are no adjacent carbon-carbon double bonds in the given olefin.

输入描述:

The first line contains two integers  and  - number of carbon bonds and hydrogen molecules.

The second line contains one string containing only  and  , representing the olefin.

输出描述:

Output one line containing the answer modulo .

示例1

输入

复制

11 2
10101010101

输出

复制

示例2

输入

复制

5 3
10010

输出

复制

备注:

It is guaranteed that ,and there are no two adjacent s in the string.

Also, it is guaranteed that the compound is an olefin, that is, there is at least one carbon-carbon double bond in it.