#include <bits/stdc++.h>
using namespace std;
const int ptbl[] = {2,  3,  5,  7,  11, 13, 17, 19, 23, 29,
                    31, 37, 41, 43, 47, 53, 59, 61, 67};
int n, a[100005], sta[16][100005];
long long tp[100005][1 << 4], f[16][1 << 4], g[100005][2][1 << 4];
vector<int> tbl[16];
inline void init() {
  memset(sta, 0, sizeof(sta));
  for (int kd = 0; kd <= 15; kd++) {
    for (int i = 0; i < tbl[kd].size(); i++) {
      while (tbl[kd][i] % 2 == 0) {
        tbl[kd][i] /= 2;
        sta[kd][i] ^= 1 << 0;
      }
      while (tbl[kd][i] % 3 == 0) {
        tbl[kd][i] /= 3;
        sta[kd][i] ^= 1 << 1;
      }
      while (tbl[kd][i] % 5 == 0) {
        tbl[kd][i] /= 5;
        sta[kd][i] ^= 1 << 2;
      }
      while (tbl[kd][i] % 7 == 0) {
        tbl[kd][i] /= 7;
        sta[kd][i] ^= 1 << 3;
      }
    }
  }
  memset(tp, 0, sizeof(tp));
  memset(f, 0, sizeof(f));
  if (tbl[0].size()) {
    tp[0][0] += 1;
    tp[0][sta[0][0]] += 1;
    for (int i = 1; i < tbl[0].size(); i++) {
      for (int s = 0; s < 1 << 4; s++) {
        tp[i][s ^ sta[0][i]] =
            (tp[i][s ^ sta[0][i]] + tp[i - 1][s]) % 1000000007;
        tp[i][s] = (tp[i][s] + tp[i - 1][s]) % 1000000007;
      }
    }
    memcpy(f[0], tp[tbl[0].size() - 1], sizeof(f[0]));
  } else {
    f[0][0] = 1;
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    bool ok = 0;
    for (int j = 18; j >= 4; j--)
      if (a[i] && a[i] % ptbl[j] == 0) {
        tbl[j - 3].push_back(a[i]);
        ok = 1;
        break;
      }
    if (!ok && a[i]) tbl[0].push_back(a[i]);
  }
  init();
  for (int kd = 1; kd <= 15; kd++) {
    if (!tbl[kd].size()) {
      memcpy(f[kd], f[kd - 1], sizeof(f[kd]));
      continue;
    }
    memset(g, 0, sizeof(g));
    for (int s = 0; s < 1 << 4; s++) {
      g[0][0][s] = (g[0][0][s] + f[kd - 1][s]) % 1000000007;
      g[0][1][s ^ sta[kd][0]] =
          (g[0][1][s ^ sta[kd][0]] + f[kd - 1][s]) % 1000000007;
    }
    for (int i = 1; i < tbl[kd].size(); i++) {
      for (int s = 0; s < 1 << 4; s++) {
        g[i][0][s ^ sta[kd][i]] =
            (g[i][0][s ^ sta[kd][i]] + g[i - 1][1][s]) % 1000000007;
        g[i][1][s ^ sta[kd][i]] =
            (g[i][1][s ^ sta[kd][i]] + g[i - 1][0][s]) % 1000000007;
        g[i][0][s] = (g[i][0][s] + g[i - 1][0][s]) % 1000000007;
        g[i][1][s] = (g[i][1][s] + g[i - 1][1][s]) % 1000000007;
      }
    }
    memcpy(f[kd], g[tbl[kd].size() - 1][0], sizeof(f[kd]));
  }
  printf("%lld\n", f[15][0] - 1);
  return 0;
}
