AT_abc209_c [ABC209C] Not Equal

题目描述

给定一个长度为 $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$ 取模后的结果。

输入格式

输入以如下格式从标准输入中给出。

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

输出格式

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

输入输出样例 #1

输入 #1

2
1 3

输出 #1

2

输入输出样例 #2

输入 #2

4
3 3 4 4

输出 #2

12

输入输出样例 #3

输入 #3

2
1 1

输出 #3

0

输入输出样例 #4

输入 #4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

输出 #4

405924645

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 10^9$
• 输入均为整数

样例解释 1

满足所有条件的 $A$ 有 $2$ 个，分别为 $(1,2)$ 和 $(1,3)$。例如 $A=(1,1)$ 不满足第二个条件。

样例解释 3

不存在满足所有条件的整数序列，因此应输出 $0$。

样例解释 4

请注意，输出时需要对 $10^9+7$ 取模。

由 ChatGPT 4.1 翻译