#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;
const int mmod = 1000000007;
const int max_n = 2222;
const int small_cnt = 15;
const int small_prime[small_cnt] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
int main()
{
int n;
scanf("%d", &n);
vector<int> mask[max_n+1];
for (int i=0; i<n; i++) {
int temp;
scanf("%d", &temp);
int bit = 0;
for (int j=0; j<small_cnt; j++) {
int occ = 0;
while (temp % small_prime[j] == 0) {
occ = 1;
temp /= small_prime[j];
}
if (occ) bit |= 1 << j;
}
for (int j=50; j<=max_n; j++)
if (j * j == temp) temp = j;
mask[temp].push_back(bit);
}
int prv[1<<small_cnt] = {0};
prv[0] = 1;
// stage 1. mask[1]
for (int i=0; i<mask[1].size(); i++) {
int bit = mask[1][i];
for (int j=(1<<small_cnt)-1; j>=0; j--) {
if ((j&bit) == bit) {
prv[j] = prv[j] + prv[j-bit];
if (prv[j] >= mmod) prv[j] -= mmod;
}
}
}
// stage 2. mask[50++]
for (int i=50; i<=max_n; i++) {
if (!mask[i].size()) continue;
// select 0 or 1 of them.
int nxt[1<<small_cnt];
for (int j=0; j<(1<<small_cnt); j++) nxt[j] = prv[j];
for (int j=0; j<mask[i].size(); j++) {
int bit = mask[i][j];
for (int k=0; k<(1<<small_cnt); k++)
if ((k&bit) == bit) {
nxt[k] = nxt[k] + prv[k-bit];
if (nxt[k] >= mmod) nxt[k] -= mmod;
}
}
for (int j=0; j<(1<<small_cnt); j++) prv[j] = nxt[j];
}
int res = mmod - n - 1;
for (int i=0; i<(1<<small_cnt); i++)
res = (res + prv[i]) % mmod;
printf("%d\n", res);
}
