CF895C Square Subsets

Petya 也因为上课迟到受到了惩罚。老师给了他一个额外任务。对于某个数组 $a$，Petya 需要找出有多少种不同的方法选择非空子集，使得所选元素的乘积等于某个整数的平方。 如果两种选择方法所选元素的下标集合不同，则认为是不同的方法。 由于答案可能非常大，你需要输出答案对 $10^9+7$ 取模后的结果。

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的元素个数。 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 70$），表示数组的元素。

输出一个整数，表示选择若干元素使得乘积为完全平方数的不同方法数（对 $10^9+7$ 取模）。

在第一个样例中，无论怎样选择元素，所有元素的乘积都是 $1$，而 $1 = 1^2$。因此答案为 $2^{4}-1=15$。 在第二个样例中，有六种不同的方法可以选择元素，使得它们的乘积为 $4$，只有一种方法使乘积为 $16$。因此答案为 $6+1=7$。 由 ChatGPT 5 翻译