题目描述

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

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

条件：对于任意满足 $1 \leq i < j \leq N$ 的 $i$ 和 $j$，有 $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)$ 取模的结果。