問題文

長さ $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)$ で割った余りを出力することに注意してください。