← 返回题目列表

Codeforces · 895/C

C. 平方子集

中文机器翻译题面 查看原题

Petya 上课也迟到了。老师给了他一项额外的任务。对于某些数组,Petya 应该找到多种不同的方法来从中选择元素的非空子集,使得它们的乘积等于某个整数的平方。

如果两种方式选择的元素索引集不同,则认为两种方式不同。

由于答案可能非常大,因此您应该以 109 + 7 为模求出答案。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — 数组中的元素数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 70) — 数组的元素。

输出

打印一个整数——选择某些元素的不同方式的数量,以便它们的乘积是某个整数模 109 + 7 的平方。

示例

输入 #1

4
1 1 1 1

输出 #1

15

输入 #2

4
2 2 2 2

输出 #2

7

输入 #3

5
1 2 4 5 8

输出 #3

7

注意

在第一个示例中,以任何方式选择的元素的乘积都是 1 并且 1 = 12。所以答案是 24 - 1 = 15。

在第二个示例中,有六种不同的方法来选择元素,使其乘积为 4,只有一种方法可以使其乘积为 16。所以答案是 6 + 1 = 7。