Contest Duration: - (local time) (100 minutes) Back to Home
C - Not Equal /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• 1 \leq A_i \leq C_i\, (1 \leq i \leq N)
• A_i \neq A_j\, (1 \leq i < j \leq N)

ただし、答えは非常に大きくなる可能性があるので、(10^9+7) で割った余りを出力してください。

### 制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq 10^9
• 入力は全て整数

### 入力

N
C_1 C_2 \ldots C_N


### 入力例 1

2
1 3


### 出力例 1

2


### 入力例 2

4
3 3 4 4


### 出力例 2

12


### 入力例 3

2
1 1


### 出力例 3

0


### 入力例 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979


### 出力例 4

405924645


(10^9+7) で割った余りを出力することに注意してください。

Score : 300 points

### Problem Statement

You are given a sequence C of N integers. Find the number of sequences A of N integers satisfying all of the following conditions.

• 1 \leq A_i \leq C_i\, (1 \leq i \leq N)
• A_i \neq A_j\, (1 \leq i < j \leq N)

Since the count may be enormous, print it modulo (10^9+7).

### Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq 10^9
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \ldots C_N


### Output

Print the number of sequences A of N integers satisfying all of the following conditions, modulo (10^9+7).

### Sample Input 1

2
1 3


### Sample Output 1

2


We have two sequences A satisfying all of the conditions: (1,2) and (1,3).
On the other hand, A=(1,1), for example, does not satisfy the second condition.

### Sample Input 2

4
3 3 4 4


### Sample Output 2

12


### Sample Input 3

2
1 1


### Sample Output 3

0


We have no sequences A satisfying all of the conditions, so we should print 0.

### Sample Input 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979


### Sample Output 4

405924645


Be sure to print the count modulo (10^9+7).