10837: ABC152 - E - Flatten
[Creator : ]
Description
Given are $N$ positive integers $A_1,...,A_N$.
Consider positive integers $B_1, ..., B_N$ that satisfy the following condition.
Condition: For any $i, j$ such that $1 \leq i < j \leq N$, $A_i B_i = A_j B_j$ holds.
Find the minimum possible value of $B_1 + ... + B_N$ for such $B_1,...,B_N$.
Since the answer can be enormous, print the sum modulo ($10^9 +7$).
Consider positive integers $B_1, ..., B_N$ that satisfy the following condition.
Condition: For any $i, j$ such that $1 \leq i < j \leq N$, $A_i B_i = A_j B_j$ holds.
Find the minimum possible value of $B_1 + ... + B_N$ for such $B_1,...,B_N$.
Since the answer can be enormous, print the sum modulo ($10^9 +7$).
Input
Input is given from Standard Input in the following format:
```
$N$
$A_1$ $...$ $A_N$
```
```
$N$
$A_1$ $...$ $A_N$
```
Output
Print the minimum possible value of $B_1 + ... + B_N$ for $B_1,...,B_N$ that satisfy the condition, modulo ($10^9 +7$).
Constraints
- $1 \leq N \leq 10^4$
- $1 \leq A_i \leq 10^6$
- All values in input are integers.
- $1 \leq A_i \leq 10^6$
- All values in input are integers.
Sample 1 Input
3
2 3 4
Sample 1 Output
13
Let $B_1=6$, $B_2=4$, and $B_3=3$, and the condition will be satisfied.
Sample 2 Input
5
12 12 12 12 12
Sample 2 Output
5
We can let all $B_i$ be $1$.
Sample 3 Input
3
1000000 999999 999998
Sample 3 Output
996989508
Print the sum modulo $(10^9+7)$.