Problem Description

Given an integer sequence $ D_1, ..., D_N $ with $ N $ elements. Find the number of trees with $ N $ vertices numbered from $ 1 $ to $ N $ that satisfy the following condition, modulo $ 998244353 $.

• For any integer $ i $ between $ 1 $ and $ N $, the distance between vertex $ 1 $ and vertex $ i $ is $ D_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D_1 $ $ D_2 $ $ ... $ $ D_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

4
0 1 1 2

Sample Output #1

2

Sample Input #2

4
1 1 1 1

Sample Output #2

0

Sample Input #3

7
0 3 2 1 2 2 1

Sample Output #3

24

Notes/Hints

Notes

• A tree with $ N $ vertices is a connected undirected graph with $ N $ vertices and $ N-1 $ edges, and the distance between two vertices is the number of edges used in the shortest path between them.
• Two trees are considered different if there exist two vertices $ x $ and $ y $ such that there is an edge between $ x $ and $ y $ in one tree and no edge between $ x $ and $ y $ in the other tree.

Constraints

• $ 1 ≦ N ≦ 10^5 $
• $ 0 ≦ D_i ≦ N-1 $

Sample Explanation 1

For example, a tree with edges between $ (1,2) $, $ (1,3) $, and $ (2,4) $ satisfies the condition.

见题面 Input 部分

见题面 Output 部分