题目描述

考虑一个长为 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$ 的余数。

3
3 4 2

8

4
2 2 5 2

0

6
999999917 999999914 999999923 999999985 999999907
999999965

445098549

数据范围与约定

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