codeforces895c Square Subsets

C. Square Subsets
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.
Two ways are considered different if sets of indexes of elements chosen by these ways are different.
Since the answer can be very large, you should find the answer modulo 109 + 7.
Input
First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.
Second line contains n integers ai (1 ≤ ai ≤ 70) — the elements of the array.
Output
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.
Examples
input
Copy

4
1 1 1 1

output

15

input
Copy

4
2 2 2 2

output

7

input
Copy

5
1 2 4 5 8

output

7

Note
In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.
In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.
제목: 몇 개의 수를 제시하고 몇 개의 비공자 집합이 곱셈을 제곱수로 하는지 물어본다.
ai는 매우 작고 70 이내의 질수는 19개이기 때문에 우리는 상압 dp를 진행한다.각 수의 각 질적 인자의 개수를 미리 처리한 다음에 짝을 나누어 옮기면 된다.만약 숫자 하나가 나타나지 않았다면 바로 무시할 것이다.
짝수 번은 질인자에 영향을 주지 않으며, 홀수는 이것에 영향을 미치므로, 이질적이거나 이질적이다.
그리고 2^(cnti-1)를 곱하면 크기마다 어떻게 선택하는지 알 수 있습니다.
코드:

#include 
using namespace std;
#define ll long long
int n,a[100005],cnt[75],dp[75][(1<<19)+5],s[75],prime[19]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67},pow[100005]={1};
int main()
{
	dp[0][0]=1;
    for(int i=1,t=i;i<=70;i++,t=i)
        for(int j=0;j<19;j++)
            while(t%prime[j]==0)
                t/=prime[j],s[i]^=(1<>n;
    for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
    for(int i=1;i<=70;i++)
    {
        if(!cnt[i]) for(int j=0;j