Jack Needs Help

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M

Author:
Problem type

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 \pmod{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 ith 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

Comments

There are no comments at the moment.