# include <fstream>
# include <cstring>
# include <algorithm>
# include <vector>
 
# define baza 10000
 
using namespace std;
 
ifstream f("indep.in");
ofstream g("indep.out");
 
int dp[ 1005 ][ 1005 ];
int unu[ 1005 ];
 
int A[ 505 ];
int N;
 
inline int cmmdc(int a, int b)
{
    if(!b)
        return a;
    return
         cmmdc(b, a % b);
}
 
void citire()
{
    int i;
 
    f >> N;
    for ( i = 1 ; i <= N ; i++ )
       f >> A[ i ];
}
 
void aduna( int A[], int B[] )
{
    int i, t = 0;
    for ( i = 1 ; i <= A[ 0 ] ||  i <= B[ 0 ] || t ; i++, t = t / baza )
    {
        A[ i ] = ( t += A[ i ] + B[ i ] ) % 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 <= 1004 ; j++ )
        {
            aduna( dp[ cmmdc( A[ i ], j ) ] , 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";
    }
    */
    if ( !dp[ 1 ][ dp[ 1 ][ 0 ] ] )
		g << 0 << "\n";
    else
    {
		g << dp[ 1 ][ dp[ 1 ][ 0 ] ];
		for ( i = dp[ 1 ][ 0 ] - 1; i ; i-- )
			g << dp[ 1 ][ i ] <<"";
    }
}
 
int main()
{
    citire();
    rezolva();
    afisare();
    return 0;
}