题目描述

有一个长度为 $N$ 的整数序列 $C$。请找出满足以下所有条件的长度为 $N$ 的整数序列 $A$ 的数量:

1. $1 \leq A_i \leq C_i (1 ≤ i ≤ N)$

2. $A_i \neq A_j (1 ≤ i < j ≤ N)$

由于答案可能非常大,请将结果对 $(10^9+7)$ 取模后输出。

输入格式

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

$N$

$C_1$ $C_2$ ... $C_N$

输出格式

输出满足所有条件的序列 A 的数量,对 $(10^9+7)$ 取模后的结果。

样例

2
1 3

2

4
3 3 4 4

12

2
1 1

0

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

405924645

样例解释

【样例1说明】

满足所有条件的序列A有两个:(1,2) 和 (1,3)。
另一方面,$A=(1,1)$ 就不满足第二个条件。

【样例3说明】

没有序列 $A$ 满足所有条件,所以我们应该输出 0。

【样例说明4】

别忘了对$(10^9+7)$取模。

数据范围

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

来源

• AtCoder ABC209C