题目描述

LucidDawn 是一个数理基础强悍的男孩子。

他刚上小学一年级的时候，就独立发现了一类逻辑问题的通解。这类逻辑问题形如：

甲说：“乙说的是真话。”
乙说：“丙说的是假话。”
丙说：“甲说的是假话。”
谁说了真话，谁说了假话？

比如上面这道题，LucidDawn 瞬间就可以找到所有解：甲、乙、丙分别为“真、真、假”或“假、假、真”。

现在他想推广这个问题。

具体地，他给定一个长度为 $N$、元素均属于 $[1,N]$ 的整数序列

$$a_1,a_2,\ldots,a_N,$$

以及一个 $01$ 序列

$$b_1,b_2,\ldots,b_N，$$

表示：

• 有 $N$ 个人，编号为 $1,2,\ldots,N$；
• 若 $b_i=1$，则第 $i$ 个人说：“第 $a_i$ 个人说的是真话。”
• 若 $b_i=0$，则第 $i$ 个人说：“第 $a_i$ 个人说的是假话。”
• 你需要确定哪些人说了真话，哪些人说了假话。显然，解不一定唯一。

但他认为这还是太简单了。因此，他决定只给出 $b_1,b_2,\ldots,b_N$，希望你告诉他，有多少个元素均属于 $[1,N]$ 的整数序列 $a_1,a_2,\ldots,a_N$，使得对应的逻辑问题存在至少一组解。

由于 LucidDawn 的数理基础十分强悍，所以他只需要你给出答案对 $998244353$ 取模后的结果。

输入格式

第一行，一个正整数 $N$。

第二行，一个长度为 $N$ 的 $01$ 串，依次表示 $b_1,b_2,\ldots,b_N$。

输出格式

输出一行一个非负整数，表示答案对 $998244353$ 取模后的结果。

样例 1

样例输入 1

2
01

样例输出 1

1

样例解释 1

当且仅当 $a=[2,2]$ 时，该逻辑问题有解。

样例 2

样例输入 2

3
100

样例输出 2

8

样例解释 2

当 $a=[2,3,1]$ 时，即为题目描述中所举的例子。

共有以下 $8$ 个合法的 $a$ 序列：

1. $[1,1,1]$；
2. $[1,1,2]$；
3. $[1,3,1]$；
4. $[1,3,2]$；
5. $[2,3,1]$；
6. $[2,3,2]$；
7. $[3,1,2]$；
8. $[3,3,2]$。

样例 3

样例输入 3

5
10111

样例输出 3

1556

样例 4

样例输入 4

12
101010010101

样例输出 4

56440427

样例 5

原题面说明样例 5 见下发文件：

ex_game1.in
ex_game1.ans

但本压缩包中未包含这两个文件，因此无法补录其具体内容。

数据范围与约定

记

$$\#1=\left|\{i\mid 1\le i\le N\land b_i=1\}\right|，$$$$\#0=\left|\{i\mid 1\le i\le N\land b_i=0\}\right|。$$

对于全部数据：

$$1\le N\le 10^7。$$

测试点编号	$N\le$	特殊限制
$1\sim2$	$3$	无
$3\sim4$	$7$
$5\sim6$	$20$
$7\sim10$	$150$
$11\sim13$	$10^5$	$\#0\le2$
$14\sim17$		无
$18$	$10^7$	$\#0=0$
$19$		$\#0\le2$
$20\sim25$		无