题目描述

给定一个长度为 $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$

输出

打印满足以上条件的长度为 $N$ 的整数序列 $A$ 的数量，取模 $(10^9+7)$。

示例输入 1

2
1 3

示例输出 1

2

满足条件的序列 $A$ 有两个：$(1,2)$ 和 $(1,3)$。
另一方面，像 $A=(1,1)$ 这样的序列不满足第二个条件。

示例输入 2

4
3 3 4 4

示例输出 2

12

示例输入 3

2
1 1

示例输出 3

0

没有满足条件的序列 $A$，所以应该打印 $0$。

示例输入 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

示例输出 4

405924645

请务必打印取模 $(10^9+7)$ 的结果。