#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <iterator>
#include <bitset>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <time.h>
#include <algorithm>
#define mkp make_pair
#define inf 1000000000
#define MOD 1000000007
#define eps 1e-7
using namespace std;
typedef long long ll;
int n;
int mask[72];
ll f[2][72];
ll dp[2][1 << 20];
bool prime(int x)
{
for (int i = 2; i*i <= x; i++)
if (x%i == 0)
return 0;
return 1;
}
void init()
{
for (int i = 0; i < 72; i++)
f[0][i] = 1;
int cnt = 0;
for (int i = 2; i < 72; i++)
{
if (!prime(i))
continue;
for (int j = 1; j < 72; j++)
{
int x = j;
while (x%i == 0)
{
x /= i;
mask[j] ^= (1 << cnt);
}
}
cnt++;
}
}
int main()
{
ios_base::sync_with_stdio(0);
init();
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
f[0][x] = f[1][x] = (f[0][x] + f[1][x]) % MOD;
}
dp[0][0] = 1;
for (int i = 0; i <= 70; i++)
{
int nxt = (i + 1) % 2;
int cur = i % 2;
for (int msk = 0; msk < (1<<20); msk++)
{
dp[nxt][msk^mask[i]] = dp[nxt][msk^mask[i]] + dp[cur][msk] * f[1][i];
dp[nxt][msk] = dp[nxt][msk] + dp[cur][msk] * f[0][i];
if (dp[nxt][msk^mask[i]] >= MOD)
dp[nxt][msk^mask[i]] %= MOD;
if (dp[nxt][msk] >= MOD)
dp[nxt][msk] %= MOD;
}
for (int msk = 0; msk < (1<<20); msk++)
dp[cur][msk] = 0;
}
cout << (dp[1][0] - 1 + MOD)%MOD << endl;
}
I2RlZmluZSBfQ1JUX1NFQ1VSRV9OT19XQVJOSU5HUwojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojZGVmaW5lIG1rcCBtYWtlX3BhaXIKI2RlZmluZSBpbmYgMTAwMDAwMDAwMAojZGVmaW5lIE1PRCAxMDAwMDAwMDA3CiNkZWZpbmUgZXBzIDFlLTcKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKaW50IG47CmludCBtYXNrWzcyXTsKbGwgZlsyXVs3Ml07CmxsIGRwWzJdWzEgPDwgMjBdOwoKYm9vbCBwcmltZShpbnQgeCkKewoJZm9yIChpbnQgaSA9IDI7IGkqaSA8PSB4OyBpKyspCgkJaWYgKHglaSA9PSAwKQoJCQlyZXR1cm4gMDsKCXJldHVybiAxOwp9Cgp2b2lkIGluaXQoKQp7Cglmb3IgKGludCBpID0gMDsgaSA8IDcyOyBpKyspCgkJZlswXVtpXSA9IDE7CglpbnQgY250ID0gMDsKCWZvciAoaW50IGkgPSAyOyBpIDwgNzI7IGkrKykKCXsKCQlpZiAoIXByaW1lKGkpKQoJCQljb250aW51ZTsKCQlmb3IgKGludCBqID0gMTsgaiA8IDcyOyBqKyspCgkJewoJCQlpbnQgeCA9IGo7CgkJCXdoaWxlICh4JWkgPT0gMCkKCQkJewoJCQkJeCAvPSBpOwoJCQkJbWFza1tqXSBePSAoMSA8PCBjbnQpOwoJCQl9CgkJfQoJCWNudCsrOwoJfQp9CgppbnQgbWFpbigpCnsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7Cglpbml0KCk7CgljaW4gPj4gbjsKCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKQoJewoJCWludCB4OwoJCWNpbiA+PiB4OwoJCWZbMF1beF0gPSBmWzFdW3hdID0gKGZbMF1beF0gKyBmWzFdW3hdKSAlIE1PRDsKCX0KCWRwWzBdWzBdID0gMTsKCWZvciAoaW50IGkgPSAwOyBpIDw9IDcwOyBpKyspCgl7CgkJaW50IG54dCA9IChpICsgMSkgJSAyOwoJCWludCBjdXIgPSBpICUgMjsKCQlmb3IgKGludCBtc2sgPSAwOyBtc2sgPCAoMTw8MjApOyBtc2srKykKCQl7CgkJCWRwW254dF1bbXNrXm1hc2tbaV1dID0gZHBbbnh0XVttc2tebWFza1tpXV0gKyBkcFtjdXJdW21za10gKiBmWzFdW2ldOwoJCQlkcFtueHRdW21za10gPSBkcFtueHRdW21za10gKyBkcFtjdXJdW21za10gKiBmWzBdW2ldOwoJCQlpZiAoZHBbbnh0XVttc2tebWFza1tpXV0gPj0gTU9EKQoJCQkJZHBbbnh0XVttc2tebWFza1tpXV0gJT0gTU9EOwoJCQlpZiAoZHBbbnh0XVttc2tdID49IE1PRCkKCQkJCWRwW254dF1bbXNrXSAlPSBNT0Q7CgkJfQoJCWZvciAoaW50IG1zayA9IDA7IG1zayA8ICgxPDwyMCk7IG1zaysrKQoJCQlkcFtjdXJdW21za10gPSAwOwoJfQoJY291dCA8PCAoZHBbMV1bMF0gLSAxICsgTU9EKSVNT0QgPDwgZW5kbDsKfQ==