#include <stdio.h>
#include <vector>
using namespace std;
const int base = 10;
const int n_max = 2000020;
vector <bool> m(n_max,false);
char nr[n_max];
long long n, maxim;
int pre[1010][1000];
int sol[1000];
int temp[1000];
void flush_down_the_toilet(int A[])
{
	for (int i = 0; i < 1000; ++ i)
		A[i] = 0;
}
void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % base;
      A[0] = i - 1;
}

void sub(int A[], int B[])
{
      int i, t = 0;
      for (i = 1; i <= A[0]; i++)
              A[i] += (t = (A[i] -= B[i] + t) < 0) * base;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

void mul(int A[], int B)
{
      int i, t = 0;
      for (i = 1; i <= A[0] || t; i++, t /= 10)
             A[i] = (t += A[i] * B) % base;
      A[0] = i - 1;
}

void precalc_the_shit()
{
	pre[0][1] = 1;
	pre[0][0] = 1;
	for (int i = 1; i <= 1000; ++ i)
	{
		add(pre[i],pre[i-1]);
		mul(pre[i],2);
	}
}
void read()
{
	freopen("indep.in","r",stdin);
	freopen("indep.out","w",stdout);
	scanf(" %lld", &n);
	
	long long t;
	for (int i = 1; i <= n; ++ i)
	{
		scanf("%lld", &t);
		if (maxim < t)
			maxim = t;
		m[t] =1;
	}
}

void combinari(int A[], long long x)
{
	for (int i = 0; i <= pre[x][0]; ++ i)
		A[i] = pre[x][i];
	int kkt[1000];
	flush_down_the_toilet(kkt);
	kkt[0] = 1;
	kkt[1] = 1;
	sub(A,kkt);
	return ;
}

void solve()
{
	long long i, j;
	for (i = 2; i<= maxim; ++i)
	{
		int v = 0;
		if (nr[i] == -1)
			continue;
		if (nr[i] == 0)
			for (j = i; j <= maxim; j+=i)
			{
				if (nr[j] != -1)
					++nr[j];
				
			}
		long long k = i*i;
		for (j = i; j <= maxim; j+=i)
		{
			if (m[j]) 
					++v;
		}
		if (2*k <= 1000)
			for (j = k; j <= maxim; j+=k)
				nr[j] = -1;
		else 
			if(k<=1000)
				nr[k] = -1;
		if (nr[i]%2 == 0)
		{
			flush_down_the_toilet(temp);
			combinari(temp,v);
			add(sol,temp);
		}
		else
		{
			flush_down_the_toilet(temp);
			combinari(temp,v);
			sub(sol,temp);
		}
		/*fprintf(stderr,"DEBUG: PT I=%lld MERGE!!J =%lld\n", i, j);
		fflush(stdout);*/
	}
}

void print()
{
	for (int i = sol[0]; i > 0; --i)
		printf("%d", sol[i]);
	printf("\n");
}



int main()
{
	precalc_the_shit();
	read();
	combinari(sol, n);
	maxim = 200;
	solve();
	print();
	return 0;
}