配点 : $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)$ で割った余りを出力せよ。

2
1 3

2

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

4
3 3 4 4

12

2
1 1

0

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

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

405924645

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