T4 神奇园艺师

题目信息

时间限制: 1s

空间限制: 512M

输入文件: game.in

输出文件: game.out

题目描述

D 国王的花园里现在有 $n$ 株绿植，第 $i$ 株绿植的高度为 $a_i$，D 国王希望某些绿植的高度相同，所以请来了神奇园艺师 d。d 每次可以选择一株绿植，将它的高度乘以一个任意质数，或是除以它的一个质因数。

d 需要对自己的工作量有所预估，所以 d 需要计算，对于全部 $n$ 株绿植的 $2^n$ 个子集，d 分别至少需要多少次操作才能使得这些绿植的高度相同。答案求和并对 $10^9+7$ 取模即可。

输入格式

第一行一个正整数 $n$，表示绿植数量

第二行 $n$ 个正整数，第 $i$ 个正整数表示第 $i$ 棵绿植的高度 $a_i$

输出格式

一行一个整数，表示答案对 $10^9+7$ 取模的结果

样例

样例输入 1

2
2 4

样例输出 1

1

样例解释 1

对于子集 $\{2, 4\}$，要么将第一个绿植的高度乘以 $2$，要么将第二个绿植的高度除以 $2$，需要操作一次。而其它子集都不需要任何操作，因此答案求和并对 $10^9+7$ 取模的结果是 $(1+0+0+0)=1$

样例输入 2

3
63 28 56

样例输出 2

15

样例输入 3

10
1 2 3 4 5 6 7 8 9 10

样例输出 3

6955

数据范围与提示

对于所有数据，满足 $1 \leq n, a_i \leq 10^6$。