题目描述

输入一个由$N$个整数组成的序列$C$，输出满足以下条件的由$N$个整数组成的序列$A$的总数

• $1\\leq A_i \\leq C_i (1 \\leq i \\leq N)$
• $A_i \ eq A_j (1\\leq i \\leq j \\leq N)$

输入格式

第一行输入一个正整数: $N$ $(1 \\leq N \\leq 2 \ imes 10^5)$ 第二行输入$N$个字符: $C_1 C_2\\,...\\,C_N$ $(1 \\leq C_i \\leq 10^9)$ 所有输入的数据均为整数。

输出格式

输出满足题目所给条件的的由$N$个整数组成的序列$A$的总数 由于答案可能会很大，请将答案对$10^9 + 7$取模后输出。

样例

2 
1 3 

2 

4 
3 3 4 4 

12 

2 
1 1 

0 

提示

样例1满足题目所给的条件的序列$A$有$(1,2)$和$(1,3)$ 而$(1,1)$不满足题目所给的第二个条件

原题出处: AtCoder Beginner Contest 209 Problem C:Not Equal

by 计科20陈延忠