安全间隔

题目描述

某实验室有一排从左到右编号为 $1,2,\ldots,n$ 的工位。为了保证设备之间留有安全距离，任意两个相邻工位不能同时被使用。

现在用一个长度为 $n$ 的 01 串 $s$ 表示工位状态：

• $s_i=1$ 表示第 $i$ 个工位已经被使用；
• $s_i=0$ 表示第 $i$ 个工位目前空闲。

已经使用的工位不能撤销。你可以选择若干个空闲工位投入使用，使最终状态中不存在相邻的两个 1，并且最终使用的工位数量尽可能多。

请计算达到最大使用数量的不同方案数。两个方案不同，当且仅当至少有一个工位在两个方案中的最终状态不同。

如果初始状态已经存在相邻的两个 1，则不存在合法方案。

输入格式

第一行一个整数 $n$。

第二行一个长度为 $n$ 的 01 串 $s$。

输出格式

输出一个整数，表示最优方案数对 $998244353$ 取模后的结果。

样例 1 输入

8
10000001

样例 1 输出

3

样例 1 说明

最多还能使用两个工位。新增工位编号分别为 $(3,5)$、$(3,6)$ 或 $(4,6)$，因此共有 $3$ 种方案。

样例 2 输入

5
01100

样例 2 输出

0

数据范围与测试点说明

对于全部数据，$3\le n\le 300000$。

本题共 $10$ 个测试点，每个测试点 $10$ 分。