#include <stdio.h>
#include <string.h>
#include <set>
#include <math.h>
#include <vector>

using namespace std;

#define NMAX 1010
#define BASE 10


#define pb push_back
#define sz size()

int n;
int s[NMAX];
vector<int> prime;
vector<int> par, impar;
vector<int> adun, scad;
set<int> h;
int a[NMAX][NMAX];
int res[NMAX];
int v[NMAX];

inline void prim(int x)
{
    int d = 2, until = (int)sqrt(x)+1;
    while(d < x && d <= until)
    {
        if(!(x%d)) return;
        ++d;
    }
    if(h.find(x) == h.end()) prime.pb(x), h.insert(x);
}

void scoate(int x)
{
    for(int i = 2; i <= x; ++i)
        if(!(x%i))
            prim(i);
}

void read()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &s[i]), scoate(s[i]);
}

void back(int level, int prod, int nr)
{
    if(prod != 1 && h.find(prod) == h.end())
    {
        h.insert(prod);
        if(nr&1) impar.pb(prod);
        else     par.pb(prod);
    }
    if(level != prime.sz)
    {
        back(level+1, prod, nr);
        back(level+1, prod*prime[level], nr+1);
    }
}

inline int divsize(int x)
{
    int nr = 0;
    for(int i = 1; i <= n; ++i) nr += !(s[i]%x);
    return nr;
}

void mul(int a[NMAX], int b)
{
    int i, t = 0;
    for(i = 1; i <= a[0] || t; ++i, t /= BASE)
        a[i] = (t += a[i]*b) % BASE;
    a[0] = i-1;
}

void aduna(int a[NMAX], int b[NMAX])
{
    int i, t = 0;
    for(i = 1; i <= a[0] || i <= b[0] || t; ++i, t /= BASE)
        a[i] = (t += a[i]+b[i]) % BASE;
    a[0] = i-1;
}

void scade(int a[NMAX], int b[NMAX])
{
    int i, t = 0;
    for(i = 1; i <= a[0]; ++i)
        a[i] += (t = (a[i] -= b[i]+t) < 0) * BASE;
    for(; a[0] > 1 && !a[a[0]]; --a[0]);
}

void print(int res[NMAX])
{
    for(int i = res[0]; i; --i) printf("%d", res[i]);
    printf("\n");
}

int main()
{
    freopen("indep.in", "r", stdin);
    freopen("indep.out", "w", stdout);
    
    read();
    
    h.clear();
    back(0, 1, 0);
    par.pb(1);
    
    //for(vector<int> :: iterator it = prime.begin(); it != prime.end(); ++it) printf("%d ", *it); printf("\n");
    for(vector<int> :: iterator it = par.begin(); it != par.end(); ++it) //printf("%d ", *it); printf("\n");
        adun.pb( divsize(*it) );
    for(vector<int> :: iterator it = impar.begin(); it != impar.end(); ++it) //printf("%d ", *it); printf("\n");
        scad.pb( divsize(*it) );


    a[0][0] = 1; a[0][1] = 1;
    v[0] = v[1] = 1;
    a[1][0] = 1; a[1][1] = 2;
    for(int i = 2; i < NMAX; ++i)
    {
        memcpy(a[i], a[i-1], sizeof(a[i-1]));
        scade(a[i-1], v);
        //print(a[i-1]);
        mul(a[i], 2);
    }
    //printf("adun ");
    for(vector<int> :: iterator it = adun.begin(); it != adun.end(); ++it)
        aduna(res, a[*it]);//, print(res);//printf("%d ", *it); printf("\n");
    //printf("scad ");
    for(vector<int> :: iterator it = scad.begin(); it != scad.end(); ++it)
        scade(res, a[*it]);//, print(res);//printf("%d ", *it); printf("\n");
        
    print(res);
    
    return 0;
}