atcoder#ABC152E. [ABC152E] Flatten

[ABC152E] Flatten

配点 : 500500

問題文

NN 個の正整数 A1,...,ANA_1,...,A_N が与えられます。

次の条件を満たすような正整数 B1,...,BNB_1,...,B_N を考えます。

条件:1i<jN1 \leq i < j \leq N を満たすどのような i,ji,j についても AiBi=AjBjA_i B_i = A_j B_j が成り立つ。

このような B1,...,BNB_1,...,B_N における B1+...+BNB_1 + ... + B_N の最小値を求めてください。

ただし、答えは非常に大きくなる可能性があるため、(109+7)(10^9 +7) で割ったあまりを出力してください。

制約

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

入力

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

NN

A1A_1 ...... ANA_N

出力

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

3
2 3 4
13

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

5
12 12 12 12 12
5

全ての BiB_i11 とすればよいです。

3
1000000 999999 999998
996989508

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