409703: GYM103688 E Exclusive Multiplication
Description
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) $$$$$$
InputThe 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)$$$.
OutputOutput one integer denoting the value of the formula you calculated.
ExamplesInput4 1 2 3 2Output
20Input
5 5 6 2 3 8Output
86