3731: 座位(第六轮01)
题目描述
受疫情影响，大家在就餐的时候需要隔位就坐。
给定一个长度为τ 的01串，1表示已经有人在此就坐并开始就餐，0表示无人就坐。 为最大化就餐人数，你需要在保证隔位就坐的前提下尽可能多的安排座位。
请你计算一下有多少种方案满足要求。
输入
第一行，包含一个正整数τ。
第二行， 一个长度为τ 的01串，表示目前的就坐情况。
输出
共一行，包含一个非负整数，表示方案数。
由于方案数可能会很大，你需要输出方案数对998244353取模后的值。
样例输入 复制
3
010样例输出 复制
1提示
【样例 1 输入】
3
010
【样例 1 输出】
1
【样例 1 说明】
虽然无法分配座位，但是这仍然是一种方案。
【样例 2 输入】
4
1001
【样例 2 输出】
1
【样例 2 说明】
显然中间的空座位无论如何分配都不能保证间隔就做。
【样例 3 输入】
5
10001
【样例 3 输出】
1
【样例 3 说明】
给第三个位置分配一个人就坐，可以最大化用餐人数。
【样例 4 输入】
6
100001
【样例 4 输出】
2
【样例 4 说明】
给第三个位置或者第四个位置分配一个人就坐，可以最大化用餐人数，方案数为 2。
【样例 5 输入】
3
111
【样例 5 输出】
0
【样例 5 说明】
目前的就坐情况已经不满足间隔就坐要求，方案数为 0。
【样例 6 输入】
20
00000001000000010000
【样例 6 输出】
4
【样例 7 输入】
50
00000000010000000000000001000000000000100000001000
【样例 7 输出】
60
【样例 8 输入】
100
00000000010000000000000001000000000000100000001000000000000100000
00100000001000000000000100000001000
【样例 8 输出】
2160
【数据范围】
对于100%的数据： 3 ≤ n ≤ 300000。
本题共有10个测试点，部分测试点满足以下性质：
测试点1：n ≤ 15。
测试点2：字符串至多有 15个位置为0，其余位置为1。
测试点3：字符串只包含0。
测试点4：字符串只包含1。
测试点5：字符串只包含1个1。 测试点6：字符串只包含2个1。