#include <stdio.h>
#include <string.h>

const int DIM = 505, CFR = 500;
int ap[1005], ciur[1005], D[1005], sol[CFR], one[CFR], two[DIM][CFR], N;

void adun (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]) % 10;
	A[0] = i-1;
}

void scad (int A[], int B[])
{
	int i, t = 0;
	for (i = 1; i <= A[0]; i++)
	{
		A[i] -= B[i] + t;
		if (A[i] < 0)
		{
			t = 1;
			A[i] += 10;
		}		
	}
	for (; A[0] > 1 && A[A[0]] == 0; A[0]--);
}

void cit ()
{
	scanf ("%d", &N);
	for (int i = 1, x; i <= N; i++)
	{
		scanf ("%d", &x);
		ap[x]++;
	}	
	one[++one[0]] = 1;
	two[0][++two[0][0]] = 1;
	for (int i = 1; i <= N; i++)
	{
		memcpy (two[i], two[i-1], CFR);
		adun (two[i], two[i-1]);
		scad (two[i-1], one);
	}
	scad (two[N], one);
	memcpy (sol, two[N], CFR);
}

void erat ()
{
	for (int i = 2, j; i <= 1005; i++)
	{
		if (ciur[i] == 0)
		{
			ciur[i] = 1;			
			for (j = i+i; j <= 1005; j += i)
			{
				if (j % (i*i) == 0)
					ciur[j] = -1;
				if (ciur[j] != -1) 
					ciur[j]++;
			}			
		}
		if (ciur[i] > 0)
		{
			for (j = i; j <= 1005; j += i)
				D[i] += ap[j];			
		}	
	}	
}

void calc ()
{
	for (int i = 2; i <= 1005; i++)
		if (D[i])
		{
			if (ciur[i] & 1)
				scad (sol, two[D[i]]);
			else	
				adun (sol, two[D[i]]);
		}
	for (int i = sol[0]; i >= 1; i--)
		printf ("%d", sol[i]);
}

int main ()
{
	freopen ("indep.in", "r", stdin);
	freopen ("indep.out", "w", stdout);
	
	cit	();
	erat ();
	calc ();
	return 0;
}