#include <iostream>
#include <stdio.h>
#include <cmath>

#define clear(_x) memset( _x, 0, sizeof( _x ) )
#define cp(_x,_y) memcpy( _x, _y, sizeof( _y ) )
using namespace std;
typedef long long ll[ 2000 ];

const int bz = 1000000;

ll jeg[ 501 ];
int n;
int maxV;
int nrprm[ 1000 ];
int nrp;
int sir[ 501 ];
ll sol;

void inmc( ll &aux, int c ) {
	int ax = 0;
	for ( int i = 1; i <= aux[ 0 ] || ax; i++ ) {
		aux[ i ] *= c;
		aux[ i ] += ax;
		ax = aux[ i ] / bz;
		aux[ i ] = aux[ i ] % bz;
		if ( i > aux[0] ) aux[0] = i;
	}
}

void addc( ll &aux, int c ) {
	aux[1] += c;
	for ( int i = 1; i <= aux[0]; i++ ) {
		aux[i+1] += aux[i] / bz;
		aux[i] = aux[i] % bz;
		if ( aux[i+1] && aux[0] == i ) aux[0]++;
	}
}

void add( ll &dest, ll &a, ll &b ) {
	int ax = 0;
	ll aux; clear( aux );
	aux[ 0 ] = max( a[0], b[0] );
	for ( int i = 1; i <= aux[0] || ax; i++ ) {
		aux[i] = a[i] + b[i];
		aux[i] += ax;
		ax = aux[i] / bz;
		aux[ i ] = aux[ i ] % bz;
		if ( i > aux[0] ) aux[0] = i;
	}
	cp(dest,aux);
}

void sub( ll &dest, ll &a, ll &b ) {
	int ax = 0;
	ll aux; clear( aux );
	for ( int i = 1; i <= a[0] || ax; i++ ) {
		aux[ i ] = a[ i ] - ax - b[ i ];
		ax = 0;
		while ( aux[ i ] < 0 ) {
			aux[i] += bz;
			ax++;
		}
		if ( i > aux[ 0 ] ) aux[ 0 ] = i;
	}
	while ( !aux[ aux[0] ] && aux[0] > 1 ) aux[0]--;
	cp(dest, aux);
}


bool prime( int x ) {
	for ( int i = 2; i <= (int) sqrt(x); i++ )
		if ( x % i == 0 ) return 0;
	return 1;
}

void back( int dc, int par, int last ) {
	int m = 0;
	for ( int i = 1; i <= n; i++ )
		if ( sir[i] % dc == 0 ) m++;
	if ( !par ) add( sol, sol, jeg[ m ] );
	else        sub( sol, sol, jeg[ m ] );

	for ( int i = last+1; i <= nrp; i++ ) {
		if ( dc * nrprm[ i ] <= maxV )
			back( dc*nrprm[i], 1-par, i );
	}
}

void print_ll( ll &a ) {
	printf("%d", a[a[0]] );
	for ( int i = a[0]-1; i >= 1; i-- )
		printf("%.6lld", a[i] );
}


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

	scanf("%d\n", &n );

	for ( int i = 1; i <= n; i++ ) {
		scanf("%d\n", &sir[ i ] );
		if ( sir[i] > maxV ) maxV = sir[i];
	}

	for ( int i = 2; i <= maxV; i++ )
		if ( prime( i ) ) {
			nrp++;
			nrprm[ nrp ] = i;
		}

	jeg[0][0] = 1;
	for ( int i = 1; i <= n; i++ ) {
		cp( jeg[i], jeg[i-1] );
		inmc( jeg[i], 2 );
		addc( jeg[i], 1 );
	}

	back ( 1, 0, 0 );
	print_ll( sol );

	fclose(stdin);
	fclose(stdout);
	
	return 0;
}