#include <stdio.h>
#include <stdlib.h>
#define C 50
//char ciur[1001];
int f[1001];
int log[501][C+1],rez[C+1],aux[1001],s[C+1];
int scad(int a[],int b[])
{
    int i,o;
    o=0;
    for(i=C; i>0; i--)
    {
        a[i]=a[i]+10-b[i]-o;
        o=1-a[i]/10;
        a[i]%=10;
    }
}
int main()
{
    /*int i,j,nr;
    for(i=2; i*i<=1000; i++)
        if(ciur[i]==0)
            for(j=i*i; j<=1000; j+=i)
                ciur[j]=1;
    nr=0;
    for(i=2; i<=1000; i++)
        if(ciur[i]==0)
            nr++;
    printf("%d\n",nr); 168 de numere prime pana la 100*/
    long long nr=0;
    int i,j,o,z,n,x,cmmdc,r;
    freopen("indep.in","r",stdin);
    freopen("indep.out","w",stdout);
    log[0][C]=1;
    for(i=1; i<170; i++)
    {
        for(j=1; j<=C; j++)
            log[i][j]=log[i-1][j];
        o=0;
        for(j=C; j>0; j--)
        {
            z=log[i][j]*2+o;
            o=z/10;
            z%=10;
            log[i][j]=z;
        }
    }
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&x);
        f[x]++;
    }
    for(i=1; i<=C; i++)
        rez[i]=log[n][i];
    nr=n+1;
    for(i=2; i<=1000; i++)
    {
        z=0;
        for(j=i; j<=1000; j+=i)
            if(f[j])
            {
                z++;
                aux[z]=j;
            }
        cmmdc=aux[1];
        for(j=2; j<=z; j++){
            aux[j]/=i;
            while(aux[j])
            {
                r=cmmdc%aux[j];
                cmmdc=aux[j];
                aux[j]=r;
            }
        }
        if(z>1 && cmmdc==1)
        {
            scad(rez,log[z]);
            nr=nr-z-1;
        }
    }
    for(i=C; i>0 && nr; i--)
    {
        s[i]=nr%10;
        nr/=10;
    }
    scad(rez,s);
    for(i=1; rez[i]==0; i++);
    if(i<=C) while(i<=C) printf("%d",rez[i++]);
    else printf("0\n");

    return 0;
}