問題文

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