Jack is planning something and needs your help. Jack needs your help to finish his math homework because he slept through class and has no idea what he is doing. He is given an array $a$ which satisfies $1\le a_i\le 2\times {10}^5$ for all $i$ $(1\le i\le n)$. A new array $b$ is generated which satisfies $0\le b_i<a_i$ for all $i$ $(1\le i\le n)$. For each $b_i$, all integers in the range $[0,a_i)$ have an equal chance of being chosen.

Jack wants to know the probability that the array $b$ is beautiful.

Array $b$ is beautiful if there exists an integer $x$ such that $x\equiv b_i(\mathrm{mod}{a}_i)$ for each $i$ $(1\le i\le n)$. This probability can be represented as $\frac{p}{q}$ where $p$ and $q$ are relatively prime.

Since $p$ and $q$ might be really large, Jack would like to receive the answer as $p+q$, modulo ${10}^9+7$.

Constraints

$1\le N\le 2\times {10}^5$
$1\le a_i\le 2\times {10}^5$

Subtask 1 [15%]

$a_i$ is prime.

Subtask 2 [15%]

$N=2$

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains $N$ $(1\le N\le 2\times {10}^5)$.
The next line contains $N$ integers, the $i$th of which is $a_i$.

Output Specification

Output $p+q$, modulo ${10}^9+7$.

Sample Input 1

3
1 2 4

Sample Output 1

3

Explanation

There are $8$ total possible arrays for $b$. Only $4$ of those arrays are beautiful. They are $\{0,0,0\}$, $\{0,0,2\}$, $\{0,1,1\}$ and $\{0,1,3\}$.
The probability can be expressed as $\frac{4}{8}$ which simplifies to $\frac{1}{2}$.
$p+q=3$ so the answer is $3$.

Sample Input 2

4
83 838 8383 83838

Sample Output 2

167