当前没有测试数据。

E - 压平

得 $N$ 个正整数 $A_1,...,A_N$.

考虑满足以下条件的正整数 $B_1, ..., B_N$。

条件：对于任意 $1 \leq i < j \leq N$，满足 $A_i B_i = A_j B_j$。

找到满足条件的 $B_1,...,B_N$ 的最小可能的值 $B_1 + ... + B_N$。

因为答案可能很大，所以取模 $10^9 + 7$ 后输出。

限制条件

• $1 \leq N \leq 10^4$
• $1 \leq A_i \leq 10^6$
• 输入中的所有值都是整数

输入

从标准输入中按以下格式给出输入。

$N$

$A_1$ $...$ $A_N$

输出

输出满足条件的 $B_1,...,B_N$ 的最小可能的值 $B_1 + ... + B_N$ ，取模 $10^9 + 7$ 后的结果。

输入样例 1

3
2 3 4

输出样例 1

13

取 $B_1=6$，$B_2=4$，$B_3=3$，满足条件。

输入样例 2

5
12 12 12 12 12

输出样例 2

5

我们可以让所有的 $B_i$ 都为 $1$。

输入样例 3

3
1000000 999999 999998

输出样例 3

996989508

取模 $10^9+7$ 后输出结果。