题目描述

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

1. $1\ \leq\ A_i\ \leq\ C_i\,\ (1\ \leq\ i\ \leq\ N)$
2. $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 解释

满足所有条件的序列 $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$
• 所有输入均为整数