102092: [AtCoder]ABC209 C - Not Equal

Problem Statement

You are given a sequence $C$ of $N$ integers. Find the number of sequences $A$ of $N$ integers satisfying all of the following conditions.

• $1 \leq A_i \leq C_i\, (1 \leq i \leq N)$
• $A_i \neq A_j\, (1 \leq i < j \leq N)$

Since the count may be enormous, print it modulo $(10^9+7)$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of sequences $A$ of $N$ integers satisfying all of the following conditions, modulo $(10^9+7)$.

Sample Input 1

2
1 3

Sample Output 1

2

We have two sequences $A$ satisfying all of the conditions: $(1,2)$ and $(1,3)$.
On the other hand, $A=(1,1)$, for example, does not satisfy the second condition.

Sample Input 2

4
3 3 4 4

Sample Output 2

12

Sample Input 3

2
1 1

Sample Output 3

0

We have no sequences $A$ satisfying all of the conditions, so we should print $0$.

Sample Input 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

Sample Output 4

405924645

Be sure to print the count modulo $(10^9+7)$.

问题描述

你被给定一个包含 $N$ 个整数的序列 $C$。找出满足以下所有条件的整数序列 $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$

输出

对 $(10^9+7)$ 取模后，打印满足所有条件的整数序列 $A$ 的数量。

样例输入 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)$ 取模后输出计数。