题目描述

$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)$ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

条件を満たすような $B_1,...,B_N$ における $B_1\ +\ ...\ +\ B_N$ の最小値を $(10^9\ +7)$ で割ったあまりを出力せよ。

题目大意

给定 $N$ 个正整数 $A_1, A_2, \cdots, A_N$。

构造一个长度为 $N$ 的正整数序列 $B$，满足

• 对于任意正整数 $i,j$，有 $A_iB_i = A_jB_j$

求出序列 $B$ 各数的和的最小值，对 $10^9+7$ 取模。

3
2 3 4

13

5
12 12 12 12 12

5

3
1000000 999999 999998

996989508

提示

制約

• $1\ \leq\ N\ \leq\ 10^4$
• $1\ \leq\ A_i\ \leq\ 10^6$
• 入力中のすべての値は整数である。

Sample Explanation 1

$B_1=6$, $B_2=4$, $B_3=3$ とすると条件を満たします。

Sample Explanation 2

全ての $B_i$ を $1$ とすればよいです。

Sample Explanation 3

和を $(10^9+7)$ で割った余りを出力してください。