该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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$ 有 $2$ 个，分别为 $(1,2)$ 和 $(1,3)$。例如 $A=(1,1)$ 不满足第二个条件。

样例解释 3

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

样例解释 4

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

数据范围

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