F. Perfect Square
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Little A has a sequence of positive integers of length $$$n$$$, denoted as $$$a_1, a_2, \cdots, a_n$$$. He wishes to create another sequence of positive integers of length $$$n$$$, denoted as $$$d_1, d_2, \cdots, d_n$$$, such that $$$d_i$$$ is a divisor of $$$a_i$$$.

It is evident that $$$d_1, d_2, \cdots, d_n$$$ are not unique, so Little A hopes that the product of $$$d_1, d_2, \cdots, d_n$$$ is a perfect square $$$x = y^2$$$, where $$$y$$$ is a positive integer.

However, at this point, $$$d_1, d_2, \cdots, d_n$$$ are still not unique. Therefore, Little A wants to know the sum of $$$y$$$, the square root of the product for all possible combinations of $$$d_1, d_2, \cdots, d_n$$$ that yield a perfect square $$$x = y^2$$$, modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) representing the length of the positive integer sequence.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$), representing the positive integer sequence.

Output

Output a single line containing an integer representing the answer.

Example
Input
2
4 4
Output
11
Note

Possible cases include $$$1 \times 1 = 1, 1 \times 2 = 2, 1 \times 4 = 4, 2 \times 1 = 2, 2 \times 2 = 4, 2 \times 4 = 8, 4 \times 1 = 4, 4 \times 2 = 8, 4 \times 4 = 16$$$.

Among these, the products that are perfect squares are $$$1 \times 1 = 1, 1 \times 4 = 4, 2 \times 2 = 4, 4 \times 1 = 4, 4 \times 4 = 16$$$.

The answer is equal to $$$\sqrt{1} + \sqrt{4} + \sqrt{4} + \sqrt{4} + \sqrt{16} = 1 + 2 + 2 + 2 + 4 = 11$$$.