分数: 500 点
问题陈述
给出的是 N 正整数 A_1,...,A_N.
考虑正整数 B_1, ..., B_N 满足以下条件。
条件:对于任何 i, j 这样 1 \leq i < j \leq N, 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 be 1.
示例输入 3
3 1000000 999999 999998
示例输出 3
996989508
打印模数之和 (10^9+7).