# include <cstdio>

typedef long long ll ;
const char *FIN = "light2.in", *FOU = "light2.out" ;
const int MAX = 30 ;

ll N, sol ;
int C[2][MAX] ;
int P[MAX], bl[MAX], d[MAX] ;

int K ;

inline int euclid ( int A, int B ) {
    while ( B ) {
        int R = A % B ;
        A = B ;
        B = R ;
    }

    return A ;
}

void prec ( void ) {
    P[1] = C[1][0] = C[1][1] = 1 ;
    for (int i = 2, k = 0; i <= K; ++i, k ^= 1) {
        C[k][0] = 1;
        for (int j = 1; j <= i; ++j) {
            C[k][j] = C[k ^ 1][j - 1] + C[k ^ 1][j] ;
            P[i] += ( j & 1 ) ? C[k][j] : 0 ;
        }
    }
}


void pinex (int lvl, int X, ll see) {
    see = ( see > N ? N + 1 : see ) ;

    if (lvl == K) {
        sol += ( X & 1 ? (N / see) * P[X] : (N / see) * -P[X] ) ;
        return ;
    }

    bl[lvl] = 0, pinex ( lvl + 1, X, see ) ;
    bl[lvl] = 1, pinex ( lvl + 1, X + 1, see * d[lvl] / euclid(see, d[lvl]) );
}

int main ( void ) {
    freopen ( "light2.in", "r", stdin ) ;

    scanf ( "%lld %d", &N, &K ) ;
    for (int i = 0; i < K; ++i)
        scanf ( "%d", d + i ) ;

    prec () ;

    pinex (0, 0, 1) ;

    fprintf ( fopen ( "light2.out", "w" ) , "%lld", sol ) ;
}