← 返回题目列表

AtCoder · nikkei2019_2_qual_b

B. 树木计数

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

分数: 300 点

问题陈述

给定的是一个整数序列 D_1,...,D_N of N 元素。求模数 998244353,树木 N 顶点编号 1 to N 满足以下条件:

  • 对于每个整数 i 来自 1 to N,顶点之间的距离 1 和顶点 i is D_i.

注释

  • 一棵树 N 顶点是一个连通的无向图 N 顶点和 N-1 边,两个顶点之间的距离是它们之间的最短路径中的边数。
  • 当且仅当有两个顶点时,两棵树被认为是不同的 x 和 y 使得之间存在边缘 x 和 y 在其中一棵树中,而不是在另一棵树中。

约束

  • 1 \leq N \leq 10^5
  • 0 \leq D_i \leq N-1

输入

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

N
D_1 D_2 ... D_N

输出

打印答案。


示例输入 1

4
0 1 1 2

示例输出 1

2

例如,一棵有边的树 编号为 (1,2), (1,3),和 (2,4) 满足条件。


示例输入 2

4
1 1 1 1

示例输出 2

0

示例输入 3

7
0 3 2 1 2 2 1

示例输出 3

24