← 返回题目列表

AtCoder · arc155_f

F. 可根据需要定向

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

给你一系列 N 非负整数: D=(D_1, D_2, \dots, D_N).

查找标记树的数量 N 顶点编号 1 to N 满足以下条件,模 998244353.

  • 有一种方法可以直接 N-1 边使得每个顶点的出度 i\ (1\leq i \leq N) is D_i.

约束

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq D_i \leq N-1
  • \sum_{i=1}^{N} D_i = N-1
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
D_1 D_2 \dots D_N

输出

打印答案。


示例输入 1

4
0 1 0 2

示例输出 1

5

下面是满足条件的五棵树,以所需的方式定向。


示例输入 2

5
0 1 1 1 1

示例输出 2

125

示例输入 3

15
0 0 0 0 0 0 0 1 1 1 1 1 2 3 4

示例输出 3

63282877