小 A 有一个长度为 $n$ 的正整数序列，记作 $a_1, a_2, \dots, a_n$。他希望构造另一个长度为 $n$ 的正整数序列 $d_1, d_2, \dots, d_n$，使得 $d_i$ 是 $a_i$ 的约数。

显然，$d_1, d_2, \dots, d_n$ 并不唯一，小 A 希望 $d_1, d_2, \dots, d_n$ 的乘积是一个完全平方数 $x = y^2$，其中 $y$ 是一个正整数。

然而，此时 $d_1, d_2, \dots, d_n$ 仍然不唯一。因此，小 A 想知道对于所有能使乘积成为完全平方数 $x = y^2$ 的 $d_1, d_2, \dots, d_n$ 的组合，其乘积的平方根 $y$ 之和，结果对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示正整数序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示该正整数序列。

输出格式

输出一行，包含一个整数，表示答案。

样例

样例输入 1

2
4 4

样例输出 1

11

说明

可能的组合包括 $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$。 其中，乘积为完全平方数的有 $1 \times 1 = 1, 1 \times 4 = 4, 2 \times 2 = 4, 4 \times 1 = 4, 4 \times 4 = 16$。 答案等于 $\sqrt{1} + \sqrt{4} + \sqrt{4} + \sqrt{4} + \sqrt{16} = 1 + 2 + 2 + 2 + 4 = 11$。