← 返回题目列表

AtCoder · abc209_c

C. 不等于

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个序列 C of N 整数。求序列数 A of N 满足以下所有条件的整数。

  • 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 of N 满足以下所有条件的整数,模 (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).