#include<cstdio>
#include<vector>
#include<set>
using namespace std;
#define NMAX 256
#define PMAX 2500005
vector <int> v;
set <int> st;
set <int>::iterator it;
int n,x,k,nr,s,a[PMAX],p[PMAX];
int N[NMAX]={1},M[NMAX]={1},AUX[NMAX];
void ciur()
{
    int i,j;
    for (i=2;i<PMAX;++i)
        if (!p[i])
        {
            p[i]=1;
            for (j=2;i*j<PMAX;++j)
                ++p[i*j];
        }
}
void suma(int A[], int B[])
{
    int i,t=0;
    for (i=1;i<=A[0] || i<=B[0] || t;++i,t/=10)
        A[i]=(t+=A[i]+B[i])%10;
    A[0]=i-1;
}
void dif(int A[], int B[])
{
    int i,t=0;
    for (i=1;i<=A[0];++i,t/=10)
    {
        A[i]-=B[i]+t;
        if (A[i]<0)
            A[i]+=10, t=10;
        else
            t=0;
    }
    for (;A[0]>1 && !A[A[0]];--A[0]);
}
void pow2(int N, int A[])
{
    int i,j,t;
    A[0]=A[1]=1;
    for (i=2;i<NMAX;++i)
        A[i]=0;
    for (j=1;j<=N;++j)
    {
        t=0;
        for (i=1;i<=A[0] || t;++i,t/=10)
            A[i]=(t+=A[i]*2)%10;
        A[0]=i-1;
    }
}
void afis(int A[])
{
    int i;
    for (i=A[0];i;--i)
        printf("%d",A[i]);
    printf("\n");
}
void dif1(int A[])
{
    int i;
    for (i=1;i<=A[0] && !A[i];++i);
    --A[i--];
    for (;i;--i)
        A[i]=0;
    for (;A[0]>1 && !A[A[0]];--A[0]);
}
int main()
{
    int i,j,d;
    freopen("indep.in","r",stdin);
    freopen("indep.out","w",stdout);
    ciur();
    scanf("%d",&n);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&x);
        for (d=2;d*d<=x;++d)
            if (x%d==0)
            {
                k=v.size();
                v.push_back(d);
                for (j=0;j<k;++j)
                    v.push_back(v[j]*d);
                while (x%d==0) x/=d;
            }
        if (x>1)
        {
            k=v.size();
            v.push_back(x);
            for (j=0;j<k;++j)
                v.push_back(v[j]*x);
        }
        for (j=0;j<v.size();++j)
            ++a[v[j]], st.insert(v[j]);
        v.clear();
    }
    for (it=st.begin();it!=st.end();++it)
        if (p[*it]&1)
        {
            pow2(a[*it],AUX);
            dif1(AUX);
            suma(N,AUX);
        }
        else
        {
            pow2(a[*it],AUX);
            dif1(AUX);
            suma(M,AUX);
        }
    dif(N,M);
    pow2(n,AUX);
    dif1(AUX);
    dif(AUX,N);
    afis(AUX);
    return 0;
}