不相等

题目描述

给定由 $N$ 个整数组成的序列 $C$。求满足以下所有条件的由 $N$ 个整数组成的序列 $A$ 的个数。

• $1 \le A_i \le C_i$（$1 \le i \le N$）
• $A_i \neq A_j$（$1 \le i \lt j \le N$）

由于个数可能很大，输出对 $(10^9+7)$ 取模的结果。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出满足所有条件的序列 $A$ 的个数对 $(10^9+7)$ 取模的结果。

样例

2
1 3

2

满足所有条件的序列 $A$ 有两个：$(1,2)$ 和 $(1,3)$。

另一方面，例如 $A=(1,1)$ 不满足第二个条件。

4
3 3 4 4

12

2
1 1

0

不存在满足所有条件的序列 $A$，所以应输出 $0$。

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

405924645

务必输出对 $(10^9+7)$ 取模后的结果。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le C_i \le 10^9$
• 输入中所有值均为整数