Problem Description

You are developing a frog-shaped robot. You have decided to have these robots race.

First, you placed $N$ robots on a number line. The robots are numbered from $1$ to $N$. Currently, the $i$-th robot is at coordinate $x_i$. Note that $x_i$ are all integers and $0 < x_1 < x_2 < ... < x_N$ holds.

You repeatedly perform the following operation:

• Choose one robot on the number line. Let the coordinate of the chosen robot be $x$. Choose a landing point from coordinates $x - 1$, $x - 2$ where there is no other robot. Make the chosen robot jump to the landing point.

If a robot's coordinate becomes 0 or less, it is considered to have reached the goal and is immediately removed from the number line. You continue performing operations until all robots have reached the goal.

Depending on how you perform the operations, there can be multiple possible sequences in which the $N$ robots reach the goal. How many possible sequences are there for the $N$ robots to reach the goal? Find the answer modulo $10^9+7$.

Input Format

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

$N$ $x_1$ $x_2$ $...$ $x_N$

Output Format

Output the number of possible sequences in which the $N$ robots reach the goal, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

4

Sample Input #2

3
2 3 4

Sample Output #2

6

Sample Input #3

8
1 2 3 5 7 11 13 17

Sample Output #3

10080

Sample Input #4

13
4 6 8 9 10 12 14 15 16 18 20 21 22

Sample Output #4

311014372

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $x_i$ are integers.
• $0 < x_1 < x_2 < ... < x_N \leq 10^9$

Partial Points

• For $500$ points, $N \leq 8$ holds.

Sample Explanation 1

There are $4$ possible sequences for the $3$ robots to reach the goal:
- $(Robot\ 1 \rightarrow Robot\ 2 \rightarrow Robot\ 3)$
- $(Robot\ 1 \rightarrow Robot\ 3 \rightarrow Robot\ 2)$
- $(Robot\ 2 \rightarrow Robot\ 1 \rightarrow Robot\ 3)$
- $(Robot\ 2 \rightarrow Robot\ 3 \rightarrow Robot\ 1)$

Sample Explanation 2

There are $6$ possible sequences for the $3$ robots to reach the goal:
- $(Robot\ 1 \rightarrow Robot\ 2 \rightarrow Robot\ 3)$
- $(Robot\ 1 \rightarrow Robot\ 3 \rightarrow Robot\ 2)$
- $(Robot\ 2 \rightarrow Robot\ 1 \rightarrow Robot\ 3)$
- $(Robot\ 2 \rightarrow Robot\ 3 \rightarrow Robot\ 1)$
- $(Robot\ 3 \rightarrow Robot\ 1 \rightarrow Robot\ 2)$
- $(Robot\ 3 \rightarrow Robot\ 2 \rightarrow Robot\ 1)$

For example, by performing operations as shown in the figure, the robots reach the goal in the sequence $(Robot\ 3 \rightarrow Robot\ 2 \rightarrow Robot\ 1)$.

Sample Explanation 4

Output the answer modulo $10^9+7$. Note that this case is not included in the partial points test cases.

见题面 Input 部分

见题面 Output 部分