#include <fstream>
using namespace std;
ifstream cin("indep.in");
ofstream cout("indep.out");
const int lim=505;
int v[lim],ok[1005];
struct numar
{
    int l;
    int a[300];
}rasp,zero,unu,doi;
numar adun(numar x,numar y)
{
    int carry=0,lim2=max(x.l,y.l);
    x.l=lim2;
    for(int i=1;i<=lim2;++i)
    {
        carry=x.a[i]+y.a[i]+carry;
        x.a[i]=carry%10;
        carry/=10;
    }
    while(carry)
        x.a[++x.l]=carry%10,carry/=10;
    return x;
}
numar scad(numar x,numar y)
{
    int carry=0;
    for(int i=1;i<=x.l;++i)
    {
        carry=x.a[i]-y.a[i]-carry;
        if(carry<0) x.a[i]=carry+10,carry=1;
        else x.a[i]=carry,carry=0;
    }
    while(x.a[x.l]==0 and x.l>0)
        --x.l;
    if(x.l==0)
        return zero;
    return x;
}
numar prod(numar x,numar y)
{
    int carry=0;
    numar t=zero;
    for(int i=1;i<=x.l;++i)
    for(int j=1;j<=y.l;++j)
        t.a[i+j-1]+=x.a[i]*y.a[j];
    t.l=x.l+y.l-1;
    for(int i=1;i<=t.l;++i)
    {
        carry=t.a[i]+carry;
        t.a[i]=carry%10;
        carry/=10;
    }
    while(carry)
        t.a[++t.l]=carry%10,carry/=10;
    return t;
}
numar power(int b)
{
    if(b==0)
        return unu;
    if(b==1)
        return doi;
    numar x=power(b/2);
    if(b%2==0)
        return prod(x,x);
    return prod(prod(x,x),doi);
}
void afis(numar x)
{
    for(int i=x.l;i>=1;--i)
        cout<<x.a[i];
}
int main()
{
    int n,maxx=0;
    cin>>n;
    zero.l=unu.l=doi.l=1;
    zero.a[1]=0; unu.a[1]=1; doi.a[1]=2;
    rasp=scad(power(n),unu);
    for(int i=1;i<=n;++i)
        cin>>v[i],maxx=max(maxx,v[i]);
    for(int i=2;i<=maxx;++i)
    if(ok[i]==0)
    {
        ok[i]=1;
        for(int j=2*i;j<=maxx;j+=i)
        if(j%(i*i)!=0) ok[j]++;
        else ok[j]=-1000000;
    }
    for(int i=2;i<=maxx;++i)
    if(ok[i]>0)
    {
        int nr=0;
        for(int j=1;j<=n;++j)
        if(v[j]%i==0) ++nr;
        if(nr==0) continue;
        if(ok[i]%2==0) rasp=adun(rasp,scad(power(nr),unu));
        else rasp=scad(rasp,scad(power(nr),unu));
    }
    afis(rasp);
    return 0;
}