#include<bits/stdc++.h>
using namespace std;

ifstream fin("indep.in");
ofstream fout("indep.out");

const int BAZA=100000;
const int NMAX=505;
const int XMAX=1005;
const int LIMIT=1005;

int n,a[NMAX];
int dp[XMAX][LIMIT];
int aux[5];

inline void ADUNA(int *b,int *c)
{
    int i,t=0,length;
    length=max(b[0],c[0]);
    for (i=1;i<=length;i++)
        {
           b[i]=b[i]+c[i]+t;
           t=0;
           if (b[i]>=BAZA) {b[i]-=BAZA;t=1;}
        }
    b[0]=length;
    if (t!=0) b[++b[0]]=1;
}

inline int NUMARA(int x)
{
    if (x==0) return 0;
    else return 1+NUMARA(x/10);
}

int main()
{
    int i,j,rez;
    fin>>n;
    for (i=1;i<=n;i++) fin>>a[i];
    aux[0]=aux[1]=1;
    for (i=1;i<=n;i++)
        {
            for (j=1;j<=1000;j++)
                {
                    rez=__gcd(a[i],j);
                    ADUNA(dp[rez],dp[j]);
                }
            ADUNA(dp[a[i]],aux);
        }
    if (dp[1][0]!=0)
        for (i=dp[1][0];i>=1;i--)
            {
                if (i<dp[1][0])
                    {
                        rez=NUMARA(dp[1][i]);
                        while (rez<5)
                            {
                                fout<<"0";
                                rez++;
                            }
                    }
                fout<<dp[1][i];
            }
    else fout<<"0";
    fout<<"\n";
    return 0;
}