题目描述

Given are $N$ positive integers $A_1,...,A_N$.

Consider positive integers $B_1, ..., B_N$ that satisfy the following condition.

Condition: For any $i, j$ such that $1 \leq i \lt j \leq N$, $A_i B_i = A_j B_j$ holds.

Find the minimum possible value of $B_1 + ... + B_N$ for such $B_1,...,B_N$.

Since the answer can be enormous, print the sum mod ($10^9 +7$).

已知有 $N$ 个正整数 $A_1,...,A_N$ 。

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

条件：对于任意 $i, j$ ， $1 \leq i \lt j \leq N$ ， $A_i B_i = A_j B_j$ 成立。

求这样的 $B_1,...,B_N$ 的 $B_1 + ... + B_N$ 的最小可能值。

由于答案可能很大，请打印模乘和 ( $10^9 +7$ )。

输入格式

输入内容按以下格式标准输入：

$N$
$A_1$ $...$ $A_N$

输出格式

打印满足条件的 $B_1,...,B_N$ 中 $B_1 + ... + B_N$ 的最小值，模数为 ( $10^9 +7$ )。

样例 #1

样例输入 #1

3
2 3 4

样例输出 #1

13

样例 #2

样例输入 #2

5
12 12 12 12 12

样例输出 #2

5

样例 #3

样例输入 #3

3
1000000 999999 999998

样例输出 #3

996989508

说明

数据规模与约定

• $1 \leq N \leq 10^4$
• $1 \leq A_i \leq 10^6$
• 所有输入值均为整数。

样例 $1$ 解释

让 $B_1=6$ 、 $B_2=4$ 和 $B_3=3$ ，即可满足条件。

样例 $2$ 解释

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

样例 $3$ 解释

打印取模 $(10^9+7)$ 的和。