题目描述

受疫情影响，大家在就餐的时候需要隔位就坐。

给定一个长度为n的01串，1表示已经有人在此就坐并开始就餐，0表示无人就坐。

为最大化就餐人数，你需要在保证隔位就坐的前提下尽可能多的安排座位。

请你计算一下有多少种方案满足要求。

输入格式

第一行，包含一个正整数n。

第二行，一个长度为n的01串，表示目前的就坐情况。 ​

输出格式

共一行，包含一个非负整数，表示方案数。

由于方案数可能会很大，你需要输出方案数对 $998244353$ 取模后的值。

样例

3
010

1

【说明】

虽然无法分配座位，但是这仍然是一种方案。

4
1001

1

【说明】

显然中间的空座位无论如何分配都不能保证间隔就做。

5
10001

1

【说明】

给第三个位置分配一个人就坐，可以最大化用餐人数。

6
100001

2

【说明】

给第三个位置分配一个人就坐，可以最大化用餐人数。

3
111

0

【说明】

目前的就坐情况已经不满足间隔就坐要求，方案数为0。

20
00000001000000010000

4

50
00000000010000000000000001000000000000100000001000

60

100
0000000001000000000000000100000000000010000000100000000000010000000100000001000000000000100000001000

2160

数据范围与提示

对于 $100\%$ 的数据：$3≤n≤300000$。

本题共有 10 个测试点，部分测试点满足以下性质：

测试点1：n≤15。

测试点2：字符串至多有15个位置为0，其余位置为1。

测试点3：字符串只包含0。

测试点4：字符串只包含1。

测试点5：字符串只包含1个1。

测试点6：字符串只包含2个1。