407816: GYM102897 C BBpigeon Counting Trees

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. BBpigeon Counting Treestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You're given a tree with $$$n$$$ nodes, labeled from $$$1$$$ to $$$n$$$, node $$$1$$$ is the root of the given tree.

The depth of $$$i$$$-$$$th$$$ node is the number of nodes in the path between root and the $$$i$$$-$$$th$$$ node including itself.

Given the depth of each node, please calculate the number of different trees meet the description.

Two trees are considered different iff there exist a node $$$x$$$ have different number of sons in these trees.

Input

First line contains a positive integer $$$n(1\le n \le 10^5)$$$, the number of nodes.

Second line contains $$$n$$$ integers $$$a_i(1 \leq n \leq 10^5)$$$, the $$$i$$$-$$$th$$$ integer is the depth of node $$$i$$$.

Output

Print the number of different tree staisfing the description above.

Since the answer could be quite large, you should just module the answer with $$$998244353$$$.

ExamplesInput
3
1 2 2
Output
1
Input
4
1 2 2 3
Output
2
Note

tree(1) and tree(2) are considered different since $$$3$$$-$$$th$$$ node have different number of sons in these trees.

tree(1) and tree(3) are the same because all nodes have same number of sons in both trees.

加入题单

上一题 下一题 算法标签: