#include <fstream>
#include <cstring>

#define maxn 501
#define maxv 1001
#define base 10

using namespace std;

ifstream fin("indep.in");
ofstream fout("indep.out");

bool sieve[maxv];
int v[maxv],p[maxn],fac[maxv],nr[maxv],mark[maxv];
int large[maxn][maxn],ans[maxn];
int t,maxval,tt,n,x;
long long prod,s;

void erathostenes (int n)
{
    for (int i=2; i<=n; ++i)
    {
        int ok=0;
        if (!sieve[i])
        {
            for (int j=i; j<=n; j+=i)
            {
                sieve[j] = 1;
                nr[j]++;
                ok |= v[j];
            }

            if (ok)
            {
                p[++t] = i;
            }
        }
    }
}

void back (int k)
{
    for (int i=k; i<=t; ++i)
    {
        prod *= p[i];
        if (prod > maxval)
        {
            prod /= p[i];
            break;
        }
        back (i+1);
        prod /= p[i];
    }

    if (prod > 1)
    {
        fac[++tt] = prod;
    }
}

void add (int a[], int b[])
{
    a[0] = max (a[0],b[0]);
    int t=0;

    for (int i=1; i<=a[0]; ++i)
    {
        a[i] = a[i]+b[i]+t;
        t = a[i]/base;
        a[i] %= base;
    }

    while (t)
    {
        a[++a[0]] = t;
        t/=base;
    }
}

void subtract (int a[], int b[])
{
    int t=0;

    for (int i=1; i<=a[0]; ++i)
    {
        a[i] = a[i] - b[i] - t;
        if (a[i] < 0)
                t = a[i]/base + 1;
            else t=a[i]/base;
        a[i] %= base;
        if (a[i] < 0) a[i] += base;
    }

    while (a[a[0]]==0 && a[0] > 0)
    {
        --a[0];
    }
}

void compute_powers ()
{
    int a[maxn];
    large[0][0] = 1;
    large[0][1] = 1;

    for (int i=1; i<=n; ++i)
    {
        memset (a,0,sizeof(a));

        int t=0;

        a[0] = large[i-1][0];

        for (int j=1; j<=a[0]; ++j)
        {
            a[j] = 2*large[i-1][j]+t;
            t = a[j]/base;
            a[j] %= base;
        }

        while (t)
        {
            a[++a[0]] = t%base;
            t/=base;
        }

        memcpy (large[i],a,sizeof(a));
    }

    for (int i=1; i<=n; ++i)
    {
        int c = i+1;
        for (int j=1; j<=large[i][0]; ++j)
        {
            large[i][j] -= c;
            if (large[i][j] < 0)
                c = large[i][j]/base + 1;
            else c=c/base;
            large[i][j] %= base;
            if (large[i][j] < 0) large[i][j] += base;
        }

        while (large[i][large[i][0]]==0 && large[i][0] > 0)
        {
            --large[i][0];
        }
    }
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>x;
        v[x]++;

        maxval = max (x,maxval);
    }

    erathostenes (maxval);

    prod = 1;

    back (1);

    s=0;

    for (int i=1; i<=tt; ++i)
    {
        for (int j=fac[i]; j<=maxval; j+=fac[i])
        {
             mark[fac[i]]+=v[j];
        }
    }

    compute_powers ();

    memcpy (ans,large[n],sizeof(ans));

    for (int i=2; i<=maxval; ++i)
    {
        if (nr[i]%2==0)
        {
            if (mark[i] > 1) add (ans,large[mark[i]]);
        }
    }

    for (int i=2; i<=maxval; ++i)
    {
        if (nr[i]%2)
        {
            if (mark[i] > 1) subtract (ans,large[mark[i]]);
        }
    }

    if (v[1])
    {
        int d[maxn];
        memset (d,0,sizeof(d));

        int i;
        for (i=1; v[1]; ++i)
        {
            d[i] = v[1]%base;
            v[1] /= base;
        }

        add (ans,d);
    }

    if (ans[0]==0) fout<<0;

    for (int i=ans[0]; i>=1; --i)
    {
        fout<<ans[i];
    }
}