题目描述

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

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

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

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

输入

第一行一个整数$N$

第二行表示一个$N$个整数的序列$A$

输出

输出满足条件的 $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

提示

• $1\ \leq\ N\ \leq\ 10^4$
• $1\ \leq\ A_i\ \leq\ 10^6$