#include <cstdio>
#include <vector>

#define Nmax 510

using namespace std;

int i , j , n , nr;

int A[Nmax];;

vector < int > g[Nmax] , d[Nmax][Nmax] , total , aux;

bool ap[Nmax];

void sum(vector < int > &C, vector < int > &A , vector < int > &B)
{
    int i , T = 0;

    //for (i = B[0] + 1; i <= A[0] && A[0] > B[0]; ++i) B[++B[0]] = 0;
    //for (i = A[0] + 1; i <= B[0] && B[0] > A[0]; ++i) A[++A[0]] = 0;

    for (C[0] = max(A[0] , B[0]) , i = 1; i <= C[0]; ++i)
     C[i] = A[i] + B[i] + T , T = C[i] / 10 , C[i] %= 10;

    if (T) C[++C[0]] = T;
    else C.pop_back();
}

int cmmdc(int a , int b)
{
    int r = a % b;
    while (r)
    {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

void pascal()
{
    d[0][0].push_back(1); d[0][0].push_back(1);
    d[0][1].push_back(1); d[0][1].push_back(0);

    for (int i = 1; i <= n; ++i)
    {
        d[i][0].push_back(1); d[i][0].push_back(1);
        for (int j = 1; j <= i; ++j)
        {
            d[i][j].push_back(0);

            for (int k = 1; k <= max(d[i-1][j].size() , d[i-1][j-1].size()); ++k)
                d[i][j].push_back(0);

            sum(d[i][j] , d[i-1][j] , d[i-1][j-1]);

            d[i][j][0] = d[i][j].size() - 1;
        }

        d[i][i+1].push_back(1); d[i][i+1].push_back(0);
    }
}

void scad(vector < int > &A , vector < int > &B)
{
    int i, T = 0;

    for (i = B[0] + 1; i <= A[0]; ) if (i >= B.size()) B.push_back(0);
                                    else B[i++] = 0;
    for (i = 1; i <= A[0]; ++i)
    {
        A[i] -= B[i] + T;
        if (A[i] < 0) T = 1 , A[i] += 10; else T = 0;
    }

    while (!A[A[0]]) {A[0]--; A.pop_back();}
}



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

    for (scanf("%d", &n) , i = 1; i <= n; ++i)
        scanf("%d", &A[i]);

    for (i = 1; i <= n; ++i)
     for (j = 1; j <= n; ++j)
      if (i != j) if (cmmdc(A[i] , A[j]) == 1) g[i].push_back(j);

    pascal();

    total.push_back(0);

    for (i = 1; i <= n; ++i)
    if (!ap[i])
    {
        for (nr = 2; nr <= n; ++nr)
        {
            aux.clear();

            for (j = 0; j <= d[n-1][nr-1][0]; ++j)
                 aux.push_back(d[n-1][nr-1][j]);

            if (n-g[i].size()-1 >= nr-1)
                scad(aux , d[n-g[i].size()-1][nr-1]);

            for (j = total[0] + 1; j <= max(total[0] , aux[0]) + 1; ++j)
                total.push_back(0);

            sum(total , total , aux);
        }

        for (j = 0; j < g[i].size(); ++j)
            ap[g[i][j]] = true;
    }

    if (total[0]) for (i = total[0]; i >= 1; --i) printf("%d", total[i]);
    else printf("0\n");


    return 0;
}