UOJ Logo Universal Online Judge

UOJ

#748. 【UNR #6】机器人表演

附件下载 统计

在这个科技发达的年代,真人表演已经落伍了。参加完 UOI 后,hehe 蚤去到了下山市大剧院,观看下山市最火爆的机器人表演。

机器人有时比人类更能抓住事情的本质。所谓表演,其实也就是开场有若干个机器人,中间有时一些机器人出现,有时一些机器人消失,最后谢幕还剩若干个机器人的过程。

hehe 蚤得到了一份公开的节目单。这份节目单介绍了按照时间顺序的一些事件。事件共有两种,一种是“某个机器人出现在了舞台上”,另一种是“某个机器人从舞台上消失了”。

但节目单上没有记录开场时会有多少个机器人,也没有记录谢幕时会有多少个机器人。

除此之外,还有 $t$ 个临时安排的机器人会来这次表演。hehe 蚤并不知道他们何时会来,何时会消失(但它们一定会来也一定会消失)。

hehe 蚤决定按照时间顺序记录整个表演。他会用 0 表示一个机器人出现在舞台上,用 1 表示一个机器人从舞台上消失,如此形成一个 01 串。

在表演开始前,hehe 蚤想知道最终 01 串共有多少种可能性。答案对 $998244353$ 取模。

简要题意:

有一个长为 $n$ 的 01 串,你需要计算 $t$ 次操作后能得到多少不同的 01 串。

一次操作的定义为:在串中选两个位置插入一对 01 使得 01 前。

输入格式

第一行为两个整数 $n, t$,表示公开的节目单上记录的事件数,与临时安排的机器人数。

第二行为一个长度为 $n$ 的 01 串 $S$ 来描述公开的节目单, 0 表示一个机器人出现在舞台上,1 表示一个机器人从舞台上消失。

节目一开始可能有些机器人就在舞台上,结束了也可能还有机器人没有离开,所以任意的 $S$ 都有对应的可行的表演过程。

输出格式

一行,用一个整数表示答案。

样例一

input

3 1
101

output

4

explanation

$4$ 种可能的 01 串分别为 01011011011001110101

样例二

input

10 5
1011001101

output

26525

样例三

input

15 47
001001000001001

output

823565713

数据范围

子任务编号 $n \leq$ $t \leq$ 分值
$1$ $10$ $5$ $10$
$2$ $10$ $50$ $20$
$3$ $20$ $50$ $15$
$4$ $100$ $5$ $15$
$5$ $100$ $100$ $15$
$6$ $300$ $300$ $25$

对于所有数据,保证 $1 \leq n, t \leq 300$。

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$