展平

题目描述

给定 $N$ 个正整数 $A_1,...,A_N$。

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

条件:对任意满足 $1 \leq i \lt j \leq N$ 的 $i,j$,都有 $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)$ 的余数。

样例

3
2 3 4

13

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

5
12 12 12 12 12

5

所有 $B_i$ 都取 $1$ 即可。

3
1000000 999999 999998

996989508

请输出和对 $(10^9+7)$ 取模的余数。

数据范围

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