#include <cstdio>
#include <cstring>
#include <algorithm>

#define MAXN 502
#define MAXV 1001

using namespace std;

struct bigNumber{
    short int s[MAXN/2], length;
} combinations[2][MAXN], answer, allcomb[MAXN];

int frq[MAXV], sieve[MAXV], bad[MAXV], total[MAXV];

inline void addUp(bigNumber &a, bigNumber &b)
{
    int i, carry = 0, limit = max(a.length, b.length);

    a.length = limit;
    for(i=0; i<limit; ++i) {
        a.s[i] += b.s[i] + carry;
        carry = a.s[i]/10;
        a.s[i] %= 10;
    }

    while(carry) {
        a.s[a.length++] = carry%10;
        carry /= 10;
    }
}

inline void take(bigNumber &a, bigNumber &b)
{
    int i;

    for(i=0; i<a.length; ++i) {
        if(a.s[i] < b.s[i]) {
            a.s[i] += 10;
            a.s[i+1]--; }
        a.s[i] -= b.s[i]; }

    while(a.length > 1 && a.s[a.length-1] == 0)
        a.length--;
}

void precompute(int n)
{
    int i, j;

    combinations[1][0].s[0] = 1;
    combinations[1][0].length = 1;
    combinations[1][1].s[0] = 1;
    combinations[1][1].length = 1;
    allcomb[1].s[0] = 1;
    allcomb[1].length = 1;

    for(i=2; i<=n; ++i)
    {
        combinations[i&1][0].s[0] = 1;
        combinations[i&1][0].length = 1;

        for(j=1; j<=i; ++j) {
            memset(combinations[i&1][j].s, 0, sizeof combinations[i&1][j].s);
            combinations[i&1][j].length = 0;

            addUp(combinations[i&1][j], combinations[(i-1)&1][j-1]);
            addUp(combinations[i&1][j], combinations[(i-1)&1][j]);
            addUp(allcomb[i], combinations[i&1][j]); }
    }
}

int main()
{
    freopen("indep.in", "r", stdin);
    freopen("indep.out", "w", stdout);

    int n, i, j, x, maxv = 0;

    scanf("%d", &n);

    for(i=1; i<=n; ++i) {
        scanf("%d", &x);
        maxv = max(maxv, x);
        frq[x]++;
    }

    precompute(n);

    addUp(answer, allcomb[n]);

    x = maxv;
    for(i=2; i<=maxv; ++i)
        for(j=i; j<=maxv; j+=i)
            total[i] += frq[j];

    for(i=2; i<=x; ++i) {
        if(!sieve[i]) {
            for(j=i; j<=x; j+=i)
                sieve[j]++;
            for(j=i*i; j<=x; j+=i*i)
                bad[j] = 1; } }

    for(i=2; i<=x; ++i) {
        if(bad[i]) continue;
        if(sieve[i]&1)
            take(answer, allcomb[total[i]]);
        else addUp(answer, allcomb[total[i]]); }

    for(i=answer.length-1; i>=0; --i)
        printf("%d", (int)answer.s[i]);

    return 0;
}