using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "indep";
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");


const int BAZ = 1e9;

void add(int a[18], int b[18])
{
   int cnt = 0;
   for (int i = 0; i < 18; ++i)
   {
      cnt += a[i] + b[i];
      a[i] = cnt % BAZ;
      cnt /= BAZ;
   }
}

void sub(int a[18], int b[18])
{
   int cnt = 0, rest = 0;
   for (int i = 0; i < 18; ++i)
   {
      cnt += a[i]-rest - b[i];
      rest = 0;
      if (cnt < 0)   cnt += BAZ, rest++;
      a[i] = cnt % BAZ;
      cnt /= BAZ;
   }
}

void add(int c[18], int a[18], int b[18])
{
   memcpy(c, a, 18*4);
   add(c, b);
}



int comb[501][501][18];

void genComb()
{
   for (int i = 0; i <= 500; ++i)
      comb[i][0][0] = comb[i][i][0] = 1;
   for (int i = 1; i <= 500; ++i)
      for (int j = 1; j < i; ++j)
         add(comb[i][j], comb[i-1][j], comb[i-1][j-1]);
}


char M[1001];

void genMobius()
{
   M[1] = 1;
   for (int i = 1; i <= 1000; ++i)
      for (int j = i+i; j <= 1000; j += i)
         M[j] -= M[i];
}



int n;
int v[501];
int fv[1001], nr[1001];


int main()
{
   genComb();
   genMobius();

   cin >> n;
   for (int i = 1; i <= n; ++i)  cin >> v[i],   fv[v[i]]++;

   for (int d = 1; d <= 1000; ++d)
      for (int i = d; i <= 1000; i += d)
         nr[d] += fv[i];
   
   int ans[18] = {};
   for (int d = 1; d <= 1000; ++d)
      for (int len = 1; len <= n; ++len)
         if (M[d] > 0)
            add(ans, comb[nr[d]][len]);
   for (int d = 1; d <= 1000; ++d)
      for (int len = 1; len <= n; ++len)
         if (M[d] < 0)
            sub(ans, comb[nr[d]][len]);
   

   bool out = 0;
   for (int i = 17; i >= 0; --i)
      if (out || ans[i])
      {
         if (out)
            for (int j = 9 - max((double) -1, log10(ans[i])); j; --j)   cout << '0';
         cout << ans[i];
         out = 1;
      }
   
   if (cout.tellp() == 0)  cout << '0';
}