今天，是JWJU给同学们分配学号的一天！为了让大家尽可能的得到自己想要的学号，鸡尾酒让大家先从 $[1,10^{18}]$ 中随机挑选一个数字作为自己的学号。但是总有一些心有灵犀的小伙伴们选择了一样的数字——显然这样是不合法的，因为每个人的学号都应该是唯一的。
于是鸡尾酒决定调整大家的学号。他采用如下两个原则来修改：
1、只增不减，每个人的最终学号 $\ge$ 每个人初始选择的学号
2、总修改量尽量少，总修改量指每一个人的改动量之和。（改动量即为最终学号减初始学号的值）
注意，修改后的最终学号可以大于$10^{18}$。
很显然，如果现在有两个同学 A 和 B，初始选择的学号均为1号，他们有可能被鸡尾酒改动成 A 同学为 $1$ 号和 B 同学为 $2$ 号，或者改动成 B 同学为 $1$ 号和 A 同学为 $2$ 号。
鸡尾酒邪魅一笑，他想让你告诉他，大家的最终学号共有多少种不同的分配方案。
第一行包含一个正整数 $n$，代表学生的数量。$(1 \le n \le 10^{5})$
接下来一行包含 $n$ 个正整数，分别代表每个学生的初始选择的学号。(取值范围$[1,10^{18}])$
输出一个整数表示最终学号的方案数。（答案对 $10^{9}+7$ 取模）
在两个最终学号的分配方案中，若存在某一个学生在两个方案中的学号不相同，则认为是这两个方案是不同的分配方案。
3 1 1 2
4
2 1 5
1
对于第一组样例，最终的学号分配方案有以下4种：
$[1,2,3], [1,3,2], [2,1,3], [3,1,2]$
分配之后每个学生的学号均不相同，且这几种方案的总修改量都是最小的。
对于第二组样例，每个学生的学号已经都不相同，所以无需修改，所以最终分配方案只有$1$种，即$[1,5]$。
Comet OJ