#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream f("indep.in");
ofstream g("indep.out");

int n,v[1005],nr[1005],tep[1005],rasp[1005],prod[1005],big[1005][1005];
int rezultat[1005],aux[1005];

int inmultire(int r)
 {
  int t=0;
  big[r+1][0]=big[r][0];
  for(int i=1;i<=big[r][0];i++,t/=10)
  {
   t+=big[r][i]*2;
   big[r+1][i]=t%10;
  }
  for(;t;t/=10)
   big[r+1][++big[r+1][0]]=t%10;
 }

int adunare(int r)
 {
  int t=0,maxim;
  maxim=max(rezultat[0],big[r][0]);
  aux[0]=maxim;
  for(int i=1;i<=maxim;i++,t/=10)
  {
   t+=big[r][i]+rezultat[i];
   aux[i]=t%10;
  }
  if(t)
   aux[++aux[0]]=t;
  for(int i=aux[0];i>=0;i--)
   {
    rezultat[i]=aux[i];
   }
 }

 int scadere(int r)
 {
  for(int i=1;i<=rezultat[0];i++)
   {
    if(big[r][i]<=rezultat[i]) rezultat[i]-=big[r][i];
    else
     {
      rezultat[i]=10+rezultat[i]-big[r][i];
      int j=i;
      while(rezultat[j+1]==0)
      {
       j++;
       rezultat[j]=9;
      }
      j++;
      rezultat[j]--;
     }
   }
  while(rezultat[rezultat[0]]==0)
    rezultat[0]--;
 }
int main()
{
f>>n;
for(int i=1;i<=n;i++)
 {
  f>>v[i];
  nr[v[i]]++;
 }
for(int i=1;i<=1000;i++)
 prod[i]=1;
rasp[1]=n;
for(int i=2;i<=1000;i++)
 {
  if(prod[i]==1)
   {
  for(int j=i;j<=1000;j+=i)
     {
    prod[j]*=i;
    tep[j]++;
     }
   }
  if(prod[i]==i)
   {
  for(int j=i;j<=1000;j+=i)
    {
    rasp[i]+=nr[j];
    }
   }
 }
big[0][0]=1; big[0][1]=1;
for(int i=0;i<=1000;i++)
 {
  inmultire(i);
  big[i][1]--;
 }
for(int i=0;i<=big[n][0];i++)
 rezultat[i]=big[n][i];
for(int i=2;i<=1000;i++)
 {
  if(rasp[i]!=0&&tep[i]%2==0)
   {
    adunare(rasp[i]);
   }
 }
for(int i=2;i<=1000;i++)
 {
  if(rasp[i]!=0&&tep[i]%2==1)
   {
    scadere(rasp[i]);
   }
 }
for(int i=rezultat[0];i>=1;i--)
 g<<rezultat[i];
if(rezultat[0]==0) g<<"0";
}