#abc209c. [abc209_c]Not Equal

[abc209_c]Not Equal

题目描述

给定一个长度为 NN 的整数序列 CC。找出满足以下条件的长度为 NN 的整数序列 AA 的数量。

  • 1AiCi(1iN)1 \leq A_i \leq C_i \, (1 \leq i \leq N)
  • AiAj(1i<jN)A_i \neq A_j \, (1 \leq i < j \leq N)

由于可能的数量很大,所以对 (109+7)(10^9+7) 取模。

约束条件

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1Ci1091 \leq C_i \leq 10^9
  • 输入中的所有值都是整数。

输入

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

NN C1C_1 C2C_2 \ldots CNC_N

输出

打印满足以上条件的长度为 NN 的整数序列 AA 的数量,取模 (109+7)(10^9+7)

示例输入 1

2
1 3

示例输出 1

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

示例输入 2

4
3 3 4 4

示例输出 2

12

示例输入 3

2
1 1

示例输出 3

没有满足条件的序列 AA,所以应该打印 00

示例输入 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

示例输出 4

405924645

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