#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;

ifstream f("indep.in");
ofstream g("indep.out");

int n, cn[1010], cp[1010], nrd[1010], maxi, a[510], X[100], A[100], s, sol[100];

void adun(int A[], int B[])
{
    int t = 0;
    if(A[0] < B[0])
        {   A[0] = B[0];
            for(int i=A[0]+1; i<=B[0]; i++) A[0] = 0;
        }
    for(int i=1; i<=A[0]; i++)
        {   t = t + A[i] + B[i];
            A[i] = t%10;
            t /= 10;
        }
    if(t) A[++A[0]] = t;
}

void scad(int A[], int B[])
{
    for(int i=B[0]+1; i<=A[0]; i++) B[i] = 0;
    for(int i=1; i<=A[0]; i++)
        {   A[i] -= B[i];
            if(A[i] < 0)
                {   A[i] += 10;
                    A[i+1]--;
                }
        }
    while(A[0] > 1 && A[A[0]] == 0) A[0]--;
}

void prod(int A[], int B[], int C[])
{
    int t = 0;
    for(int i=1; i<=A[0]; i++)
        for(int j=1; j<=B[0]; j++)
            {   C[i+j-1] += (A[i] * B[j] + t);
                t = C[i+j-1] / 10;
                C[i+j-1] %= 10;
            }
    C[0] = A[0] + B[0] - 1;
    while(t)
        {   C[++C[0]] = t%10;
            t /= 10;
        }
}

void copie(int A[], int B[])
{
    for(int i=0; i<=B[0]; i++) A[i] = B[i];
}

void putere(int A[], int n, int D[])
{
    if(n == 1) copie(D, A);
    else if(n & 1)
        {   int C[100] = {0}, E[100] = {0};
            prod(A,A,C);
            putere(C, n/2, E);
            prod(A, E, D);
        }
    else
        {   int C[100] = {0};
            prod(A,A,C);
            putere(C,n/2,D);
        }
}

long long put(long long a, int n)
{
    if(!n) return 1;
    if(n & 1) return a * put(a*a, n/2);
    return put(a*a, n/2);
}

void afis(int A[])
{
    for(int i=A[0]; i>=1; i--) g << A[i];
    g << '\n';
}

void baga(int A[], int x)
{
    while(x)
        {   A[++A[0]] = x%10;
            x /= 10;
        }
}

void ciur()
{
    for(int i=2; i<=maxi; i++)
        {   if(!cn[i])
                {   for(int j=i; j<=maxi; j+=i) cn[j]++;
                    int k = i * i;
                    for(int j=k; j<=maxi; j+=k) cp[j] = 1;
                }
            if(!cp[i] && nrd[i])
                {   if(cn[i] & 1)
                    {
                        memset(X, 0, sizeof(X));
                        putere(A, nrd[i], X);
                        s++;
                        scad(sol, X);
                        //sol = sol - (put(1LL * 2, nrd[i]) - 1);
                    }
                    else
                    {   memset(X, 0, sizeof(X));
                        putere(A, nrd[i], X);
                        s--;
                        adun(sol, X);
                        //sol = sol + put(1LL * 2, nrd[i]) - 1;
                    }
                }
        }
}

int main()
{
    f >> n;
    A[0] = 1;
    A[1] = 2;
    s = -1;
    putere(A, n, sol);
    //afis(sol);

    for(int i=1; i<=n; i++) f >> a[i], maxi = max(maxi, a[i]);
    for(int i=1; i<=n; i++)
        {   for(int j=1; j<=a[i]/2; j++)
                if(a[i] % j == 0) nrd[j]++;
            nrd[a[i]]++;
        }
    ciur();
    memset(X, 0, sizeof(X));
    if(s > 0)
        {   baga(X, s);
            adun(sol, X);
        }
    else
        {   baga(X, -s);
            scad(sol, X);
        }
    afis(sol);

    //g << sol << '\n';
    return 0;
}