You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

I - 新新的不等式

题目描述

新新很喜欢不等式。

现在他有一个长度为 $n$ 的整数序列 $b$ ，他想知道满足以下条件的长度为 $n$ 的整数序列 $a$ 的个数。

• 对于任意 $1\le i \le n$ ，满足 $1 \le a_i \le b_i$ 。
• 对于任意 $1\le i < j \le n$ ，满足 $a_i \neq a_j$ 。

由于方案数太多，只需要输出答案对 $10^9 + 7$ 取模的结果。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个整数，分别代表 $b_1 , b_2, \dots , b_n$ 。

输出格式

输出满足条件的序列 $a$ 的个数对 $10^9 + 7$ 取模的结果。

样例

输入 $1$

4
3 3 4 4

输出 $1$

12

输入 $2$

2
1 1

输出 $2$

0

输入 $3$

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

输出 $3$

405924645

数据范围

对于所有数据，保证 $1\le n \le 2\times 10^{5}$ ，$1\le b_i \le 10^{9}$ 。