在神奇的 Bubbledom 土地上，一年一度的气泡节即将举行。节日的亮点是创造特殊的“棱镜气泡”，这是通过一种结合了三种不同魔法质数精华的古老巫术形成的。

如果一个数恰好是三个不同质数的乘积，则称其为“棱镜数”。例如，$30$ 是一个棱镜数，因为 $30 = 2 \cdot 3 \cdot 5$，但 $12$ 不是棱镜数，因为它等于 $2 \cdot 2 \cdot 3$（多次使用了相同的质数）。

Bubbledom 的巫师们得到了一个由 $N$ 个魔法精华数组成的集合，每个数都由一个正整数表示。你的任务是确定这些精华数有多少个非空子集，其乘积是一个棱镜数。

由于这个数量可能很大，你应该输出它模 $10^9 + 7$ 的结果。

输入格式

第一行包含一个整数 $N$，表示气泡精华数的数量（$1 \le N \le 10^5$）。

第二行包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，表示这些精华数（$1 \le S_i \le 10^6$）。

输出格式

输出一个整数，表示乘积为棱镜数的子集数量，模 $10^9 + 7$。

样例

输入样例 1

6
1 3 3 7 21 13

输出样例 1

6

说明

在样例中，这六个子集是：

• $3, 7, 13$
• $3, 7, 13$（使用第二个 $3$）
• $21, 13$
• $1, 3, 7, 13$
• $1, 3, 7, 13$（使用第二个 $3$）
• $1, 21, 13$