题目描述

Robert 厌倦了自己的白色 T 恤，于是决定把它染成自己最喜欢的颜色：蓝色。

他的朋友 Georgian 给了他若干片蓝色染色药片，共有 $N$ 种不同的蓝色初始色调。对于第 $i$ 种色调，Robert 有 $p_i$ 片药片。

为了染色，Robert 会把 T 恤和若干药片一起放入洗衣机中。他想制造一种新的蓝色色调，于是选择整数

$$a_1,a_2,\ldots,a_N$$

其中 $a_i$ 表示使用第 $i$ 种初始色调的药片数量。要求：

$$1\le a_i\le p_i$$

也就是说，每种初始色调至少使用一片，且不能超过已有数量。

两个选择方案

$$a_1,a_2,\ldots,a_N$$

和

$$b_1,b_2,\ldots,b_N$$

会被认为染出了同一种新色调，当且仅当：

$$\frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots=\frac{a_N}{b_N}.$$

请计算 Robert 最多可以制造出多少种不同的新蓝色色调。由于答案可能很大，只需要输出答案对

$$1\,000\,000\,007$$

取模后的结果。

输入格式

第一行包含一个整数 $N$，表示初始色调的数量。

第二行包含 $N$ 个整数：

$$p_1,p_2,\ldots,p_N$$

其中 $p_i$ 表示第 $i$ 种初始色调已有的药片数量。

输出格式

输出一行一个整数，表示可以形成的不同新色调数量，对 $1\,000\,000\,007$ 取模。

数据范围与约定

记：

$$V_{\min}=\min(p_1,p_2,\ldots,p_N),\qquad V_{\max}=\max(p_1,p_2,\ldots,p_N).$$

保证：

• $1\le N\le 200000$；
• $1\le V_{\min}\le V_{\max}\le 200000$。

子任务

子任务	分值	限制
1	2	$V_{\min}=1$
2	6	$1\le N,V_{\max}\le 7$
3	4	$1\le N,V_{\max}\le 8$
4	16	$1\le N,V_{\max}\le 100$
5	11	$1\le N,V_{\max}\le 1000$
6	7	$1\le N,V_{\max}\le 5000$
7	15	$1\le N,V_{\max}\le 30000$
8	10	$V_{\min}=V_{\max}$
9	8	$1\le V_{\min}\le 100$
10	21	无额外限制

样例

样例 1

3
2 3 2

11

样例 2

4
7 7 7 7

2303

样例 3

7
15 8 19 7 15 8 19

36191027

样例 4

2
31124 150719

851838928

样例解释

对于第一个样例，共有 $11$ 种可能的新色调：

• $\langle 1,1,1\rangle$，它与 $\langle 2,2,2\rangle$ 相同；
• $\langle 1,1,2\rangle$；
• $\langle 1,2,1\rangle$；
• $\langle 1,2,2\rangle$；
• $\langle 1,3,1\rangle$；
• $\langle 1,3,2\rangle$；
• $\langle 2,1,1\rangle$；
• $\langle 2,1,2\rangle$；
• $\langle 2,2,1\rangle$；
• $\langle 2,3,1\rangle$；
• $\langle 2,3,2\rangle$。