#include <iostream>
#include <fstream>

using namespace std;

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

#define nmax 501
#define Valmax 1002
#define Cifmax 500

int n, a[nmax], dp[nmax][Valmax][Cifmax];
int Max = 0; // valoarea maxima din sir

void citeste(){

    f >> n;

    for(int i=1; i<=n; i++) f >> a[i], Max = max(Max, a[i]);

}

int cmmdc(int a, int b){

    if (b == 0) return a;
    return cmmdc(b, a%b);

}

void aduna(int a[], int b[]){

    //!!! daca schimb in b ramane si in afara procedurii
    //=> c[] = b[] si schimb doar c-ul
    //a = a + b;
    int c[Cifmax];
    for(int i=0; i<Cifmax; i++) c[i] = 0;
    for(int i=0; i<=b[0]; i++) c[i] = b[i];

    //cazul cand b[0] > a[0]
    if (c[0] > a[0]){
        for(int i=a[0]+1; i<=c[0]; i++) a[i] = 0;//pun zerouri
        a[0] = c[0];//ii zic ca acum are b[0] cifre
    } // e de ajuns atat; cazul cand a[0] >= b[0] nu ma intereseaza ca in b[0] am oricum 0

    int rest = 0;
    for(int i=1; i<=a[0]; i++){
        a[i] += c[i] + rest;
        rest = a[i] / 1000000000;//tin zecile
        a[i] = a[i] % 1000000000;//tin ultima cifra
    }

    if (rest) a[ ++a[0] ]  = rest;

}


void rezolva(){

    //nr de subsiruri pentru care cel mai mare numar care le dividie pe toate nr din subsir sa fie 1
    //dp[i][j] = numarul de subsirui din primele i avand cmmdc-ul j
    //fac metoda si inapoi si inainte :)) folosindu-ma de i-1,j;
    //trebuie numere mari :-"
    //cel mai rau caz cred ca e de genul : suma Comb de n elemente luate cate k, k = 1,n;

    for(int i=1; i<=n; i++){
        dp[i][ a[i] ][0] = 1;//initalizez dinamica  : cazul cand il iau doar pe a[i];
        dp[i][ a[i] ][1] = 1;
        for(int j=1; j<=Max; j++){//ma aflu in (i,j) continui i,j din i-1,j nu adaug a[i] si 2 : continui i,cmmdc(j,a[i]) cu i,j
            //dp[i][j] += dp[i-1][j];//nu ma folosesc a[i];
            //dp[i][ cmmdc(j,a[i]) ] += dp[i-1][j];//si acum ma folosesc de a[i];
            aduna(dp[i][j], dp[i-1][j]);
            aduna(dp[i][ cmmdc(j,a[i]) ], dp[i-1][j]);
        }
    }

    //g << dp[n][1] << "\n";
    //am numarul de forma unitati zeci, sute etc =>
    g << dp[n][1][ dp[n][1][0] ];
    for(int i=dp[n][1][0]-1; i>=1; i--){
        int x = dp[n][1][i];
        int cat = 9;
        while(x){
            --cat;
            x = x / 10;
        }
        for(; cat>0; cat--)g << 0;
        g << dp[n][1][i];
    }

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}