409703: GYM103688 E Exclusive Multiplication

Megumi is a girl who loves number theory. Today is her birthday, so Joseph creates a new function $$$f(n)$$$ and gives it to her as a gift. The definition of $$$f(n)$$$ is shown in the formula as follows.

$$$$$$ f(n) = \prod_{i = 1}^m p_i^{a_i \% 2} $$$$$$

where $$$p_1,p_2,\cdots,p_m~(p_1 < p_2 < \cdots < p_m)$$$ are prime factors of $$$n$$$ and

$$$$$$ n = \prod_{i = 1}^m p_i^{a_i} $$$$$$

Now Joseph gives you $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$ and wants you to calculate the following formula. $$$$$$ \left(\sum_{1\leq i < j \leq n} f\left(b_i \times b_j\right)\right)\mod (10^9+7) $$$$$$

The first line contains one integer $$$n~(1\leq n \leq 2 \times 10^5)$$$.

The second line contains $$$n$$$ integers $$$b_1, b_2, \cdots, b_n ~ (1 \leq b_i \leq 2 \times 10^5)$$$.

Output one integer denoting the value of the formula you calculated.

4
1 2 3 2

20

5
5 6 2 3 8

86