题目描述

長さ $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)$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

条件を全て満たす整数列 $A$ の個数を $(10^9+7)$ で割った余りを出力せよ。

题目大意

给定长度为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)$的余数。

2
1 3

2

4
3 3 4 4

12

2
1 1

0

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

405924645

提示

制約

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

Sample Explanation 1

条件を全て満たす $A$ は $(1,2)$ と $(1,3)$ の $2$ つです。 例えば $A=(1,1)$ は $2$ つ目の条件を満たしません。

Sample Explanation 3

条件を全て満たす整数列は $1$ つも存在しないので、$0$ と出力してください。

Sample Explanation 4

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