题目描述

给定一个由$N$个正整数组成的序列：$A=(A_1,A_2,\dots,A_N)$。

有多少个整数序列$B$满足以下所有条件？请以模$998244353$的形式输出结果。

• 对于每个整数$i$，满足$1 \le i \le N$，在$B$中恰好有$A_i$个$i$。
• 对于每个整数$i$，满足$1 \le i \le |B|-1$，$|B_i - B_{i+1}|=1$成立。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$
• 输入中的所有值均为整数。

输入

输入数据从标准输入读取，输入格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。

示例输入1

3
2 3 1

示例输出1

6

$B$可以是以下六个序列。

• $(1,2,1,2,3,2)$
• $(1,2,3,2,1,2)$
• $(2,1,2,1,2,3)$
• $(2,1,2,3,2,1)$
• $(2,3,2,1,2,1)$
• $(3,2,1,2,1,2)$

因此，答案是$6$。

示例输入2

1
200000

示例输出2

0

可能没有满足条件的序列。

示例输入3

6
12100 31602 41387 41498 31863 12250

示例输出3

750337372