#include <stdio.h>
/*ifstream in ("indep.in");
ofstream out ("indep.out");*/
int const M=1000;
int const N=501;
int v[N];
long long mat[N][M];

int cmmdc(int x,int y)
{
    int z;
    while(y!=0)
    {
        z=x%y;
        x=y;
        y=z;
    }
    return x%1000000000;
}

int main()
{
    int i,j,n;
    freopen("indep.in","r",stdin);
    freopen("indep.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    mat[0][0]=1;
    mat[1][v[1]]=1;
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=M;j++)
            mat[i][cmmdc(j,v[i])] += mat[i-1][j];
        for(j=0;j<=M;j++)
            mat[i][j] += mat[i-1][j];
    }
    printf("%lld",mat[n][1]%1000000000);
    return 0;
}