# include <fstream>
# include <cstring>
# include <algorithm>
# include <vector>

# define baza 1000

using namespace std;

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

short dp[ 1005 ][ 1005 ];
short unu[ 1005 ];

short A[ 505 ];
int N;

unsigned long long  cmmdc( unsigned long long X, unsigned long long Y )
{
    if ( X < Y )
       return cmmdc( X, Y - X );
    else
    if ( X > Y )
       return cmmdc( X - Y, Y );
    else
       return X;
}

void citire()
{
    int i;

    f >> N;
    for ( i = 1 ; i <= N ; i++ )
       f >> A[ i ];
}

void aduna( short A[], short B[] )
{
    int i, t = 0;
    for ( i = 1 ; i <= A[ 0 ] ||  i <= B[ 0 ] || t ; i++ )
    {
        A[ i ] = ( t += A[ i ] + B[ i ] ) % baza;
        t = t / baza;
    }
    A[ 0 ] = i - 1;
}

void rezolva()
{
    int i, j;
    int nr;

    unu[ 0 ] = unu[ 1 ] = 1;

    for ( i = 1  ; i <= N ; i++ )
    {
        for ( j = 1 ; j < 1000 ; j++ )
        {
            nr = cmmdc( A[ i ], j );
            aduna( dp[ nr ] , dp[ j ] );
        }
        //dp[ A[ i ] ] ++;
        aduna( dp[ A[ i ] ], unu );
    }
}

void afisare()
{
    int i, j;
   /* for ( i = 1 ; i <= 10 ; i++ )
    {
        for ( j = 1 ; j <= N ; j++ )
           g << dp[ i ][ j ] << " ";
        g << "\n";
    }
    */

    for ( i = dp[ 1 ][ 0 ] ; i >= 1 ; i-- )
        g << dp[ 1 ][ i ] <<"";
}

int main()
{
    citire();
    rezolva();
    afisare();
    return 0;
}