题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。

请输出满足以下所有条件的整数序列 $B$（$B$ 由 $1$ 到 $N$ 之间的整数构成）的个数，对 $998244353$ 取模。

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

输入格式

输入以以下格式从标准输入给出。

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

输出格式

请输出答案。

样例 1

输入

3
2 3 1

输出

6

样例 2

输入

1
200000

输出

0

样例 3

输入

6
12100 31602 41387 41498 31863 12250

输出

750337372

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• 输入均为整数。

样例解释 1

满足条件的 $B$ 有以下 $6$ 种：

• $(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

也有可能不存在满足条件的 $B$。

由 ChatGPT 4.1 翻译