Problem Description

Takahashi loves shortest path algorithms. He plays with various shortest path algorithms every day. However, since he has been calculating shortest paths too much, he has grown tired of it.

Therefore, Takahashi decided to count the number of undirected simple graphs with \( N \) vertices where all edge lengths are 1, such that the shortest distance from a certain vertex to other vertices takes specific values.

More precisely, Takahashi wants to count the graphs where there are no multiple edges between the same pair of vertices, and all edges connect different vertices. The vertices are numbered \( 1, 2, ..., N \). For any \( i \), the minimum number of edges on the path connecting vertex \( 1 \) and vertex \( i \) is \( A_i \).

Given integers \( N \) and \( A_1, ..., A_N \), find the number of such graphs modulo \( 10^9+7 \).

Input Format

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

\( N \) \( A_1\ A_2\ ...\ A_N \)

• The first line contains the number of vertices \( N \) (\( 1 \leq N \leq 10^5 \)).
• The second line contains the integer sequence \( A_1, ..., A_N \) (\( 0 \leq A_1, ..., A_N \leq N-1 \)) representing the shortest distances from vertex \( 1 \) to vertex \( i \), separated by spaces.

Output Format

Output the number of graphs satisfying the conditions modulo \( 10^9+7 \).

End the output with a newline. (corrected at 21:40)

Sample Input and Output

Sample Input #1

4
0 1 1 2

Sample Output #1

6

Sample Input #2

4
0 1 2 0

Sample Output #2

0

Sample Input #3

3
1 1 2

Sample Output #3

0

Sample Input #4

17
0 1 1 2 2 4 3 2 4 5 3 3 2 1 5 4 2

Sample Output #4

855391686

Notes/Hints

Sample Explanation 1

The following 6 graphs satisfy the conditions. 

Sample Explanation 2

Since all edge lengths are 1, there is no graph where the distance between vertices 1 and 4 is 0.

Sample Explanation 3

The distance from vertex 1 to vertex 1 cannot be 1.

见题面 Input 部分

见题面 Output 部分