#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;
}

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--)
            fout<<dp[1][i];
    else fout<<"0";
    fout<<"\n";
    return 0;
}