题目描述

考虑一个长为 n 的正整数数列 a1,a2,…,an。满足如下条件：

1. 1≤a_i≤c_i（1≤i≤n）

2. a_i≠a_j（1≤i<j≤n）

其中 c1,c2,…,cn 是已知的正整数。

你要求出有多少种不同的数列 a 满足条件。答案会很大，所以只需要输出答案除以 $10^{9}+7$ 的余数。

输入格式

第 1 行，1 个正整数 n。

第 2 行，n 个正整数 c1,c2,…,cn。

输出格式

输出答案除以 $10^{9}+7$ 的余数。

数据范围与约定

1≤$n\le 2\times 10^{5}$；1≤c_i≤$10^{9}$。

可见测试数据

输入数据 1

3
3 4 2

输出数据 1

8

输入数据 2

4
2 2 5 2

输出数据 2

0

输入数据 3

6
999999917 999999914 999999923 999999985 999999907
999999965

输出数据 3

445098549