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

using namespace std;

#define NMAX 1000
#define BASE 1000000000
#define FORMAT "%09d"

#define pb push_back
#define sz size()

inline int MAX(int a, int b) { return (a > b) ? (a) : (b); }

int n;
int s[1000];
vector<int> prime;
vector<int> par, impar;
vector<int> adun, scad;
set<int> h;
int a[1010][1000];
int res[1000];
int v[1000];
int _max = -0x3f3f3f3f;

inline void prim(int x)
{
    int d = 2;
    while(d < x)
    {
        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]), _max = MAX(_max, 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 != (int)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) && (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])
{
    printf("%d", res[res[0]]);
    for(int i = res[0]-1; i; --i) printf(FORMAT, res[i]);
    printf("\n");
}

void incearca(int x)
{
    int nr = 0, aux = x;
    for(vector<int> :: iterator it = prime.begin(); it != prime.end(); ++it)
        if(!(x % (*it)))
        {
            ++nr;
            x /= (*it);
            if(!(x % (*it))) return;
        }
    if(nr != 0)
    {
        if(nr & 1)
            impar.pb(aux);
        else
            par.pb(aux);
    }
}

int main()
{
    freopen("indep.in", "r", stdin);
    freopen("indep.out", "w", stdout);
    
    read();
    
    h.clear();
    //back(0, 1, 0);
    par.pb(1);
    for(int i = 2; i <= _max; ++i)
        incearca(i);
    
    //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 < 1004; ++i)
    {
        memcpy(a[i], a[i-1], sizeof(a[i-1]));
        scade(a[i-1], v);
        //print(a[i-1]);
        mul(a[i], 2);
    }
    a[0][1]--;
    //a[1][1]--;
    
    //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;
}