Flatten

AtCoder

IDabc152_e

Time2000ms

Memory256MB

Difficulty—

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$). ## Constraints * $1 \leq N \leq 10^4$ * $1 \leq A_i \leq 10^6$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $...$ $A_N$ [samples]

Samples

Input #1

3
2 3 4

Output #1

13

Let $B_1=6$, $B_2=4$, and $B_3=3$, and the condition will be satisfied.

Input #2

5
12 12 12 12 12

Output #2

5

We can let all $B_i$ be $1$.

Input #3

3
1000000 999999 999998

Output #3

996989508

Print the sum modulo $(10^9+7)$.

API Response (JSON)

{
  "problem": {
    "name": "Flatten",
    "description": {
      "content": "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_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc152_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are $N$ positive integers $A_1,...,A_N$.\nConsider positive integers $B_1, ..., B_N$ that satisfy the following condition.\nCondition: For any $i, j$ such that $1 \\leq i < j \\leq N$, $A_i B_i = A_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments