#include <fstream>
#include <iomanip>
#include <vector>
#define nmax 501
#define baza (int)1e8
using namespace std;
ifstream cin("indep.in");
ofstream cout("indep.out");
int n,x,sol[20],p[20],aux[20],nr[1001],fr1,m;
bool in[1001];
vector<int>a,e;/// divzorii primi ce se regasesc in numerele date
void produs(int a[],int b){
    int r=0;
    for(int i=1;i<=a[0];i++){
        a[i]=a[i]*b+r;
        r=a[i]/baza;
        a[i]%=baza;
    }
    while(r!=0){
        a[++a[0]]=r%baza;
        r/=baza;
    }
}
void exp(int a[],int b){
    while(b--)
        produs(a,2);
}
void initializare(int a[],int val){
    for(int i=1;i<=a[0];i++)
        a[i]=0;
    a[0]=1;
    a[1]=val;
}
void adunare(int a[],int b[]){
    int n=max(a[0],b[0]),r=0;
    for(int i=1;i<=n;i++){
        a[i]=a[i]+b[i]+r;
        r=a[i]/baza;
        a[i]%=baza;
    }
    a[0]=n;
    while(r!=0){
        a[++a[0]]=r%baza;
        r/=baza;
    }
}
void scadere(int a[],int b[]){
    for(int i=1;i<=b[0];i++){
        if(a[i]-b[i]>=0)
            a[i]-=b[i];
        else{
            int j=i+1;
            while(a[j]==0)
                a[j++]=baza-1;
            a[j]--;
            a[i]=baza-(b[i]-a[i]);
        }
    }
    while(a[0]>1&&a[a[0]]==0)
        a[0]--;
}
void afisare(int a[]){
    cout<<a[a[0]];
    for(int i=a[0]-1;i>0;i--)
        cout<<setw(8)<<setfill('0')<<a[i];
}
void add(int last,int val){
    nr[val]++;
    for(int i=last;i<m;i++)
        add(i+1,val*e[i]);
}
void pinex(int last,int val,int t){
    if(nr[val]>1){
        initializare(p,1);
        exp(p,nr[val]);
        initializare(aux,1+nr[val]);
        scadere(p,aux);
        if(t%2==0){
            ///sol-=((1<<nr[val])-1-nr[val]);
            scadere(sol,p);
        }else{
            ///sol+=((1<<nr[val])-1-nr[val]);
            adunare(sol,p);
        }
    }
    for(int i=last;i<m;i++)
        pinex(i+1,val*a[i],t+1);
}
int main()
{
    cin>>n;
    initializare(sol,0);
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x==1){
            fr1++;
            continue;
        }
        e.clear();
        for(int d=2;d*d<=x;d++)
            if(x%d==0){
                e.push_back(d);
                if(!in[d])
                    a.push_back(d);
                in[d]=1;
                while(x%d==0)
                    x/=d;
            }
        if(x!=1){
            e.push_back(x);
            if(!in[x])
                a.push_back(x);
            in[x]=1;
        }
        m=e.size();
        add(0,1);
    }
    nr[1]=0;
    m=a.size();
    pinex(0,1,0);
    initializare(aux,n-fr1+1);
    adunare(sol,aux);
    initializare(p,1);
    exp(p,n);
    scadere(p,sol);
    ///cout<<(1<<n)-1-sol-(n-fr1);
    afisare(p);
    return 0;
}