/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数列 C が与えられます。以下の条件を全て満たす長さ N の整数列 A の個数を求めてください。
- 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
出力
条件を全て満たす整数列 A の個数を (10^9+7) で割った余りを出力せよ。
入力例 1
2 1 3
出力例 1
2
条件を全て満たす A は (1,2) と (1,3) の 2 つです。 例えば A=(1,1) は 2 つ目の条件を満たしません。
入力例 2
4 3 3 4 4
出力例 2
12
入力例 3
2 1 1
出力例 3
0
条件を全て満たす整数列は 1 つも存在しないので、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).