Exclusive Multiplication

题号：NC237067
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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 .
The second line contains  integers .

输出描述:

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

示例1

输入

复制

4
1 2 3 2

输出

复制

示例2

输入

复制

5
5 6 2 3 8

输出

复制