#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MaxN = 105;
const int MaxV = 100000;

vector<int> A[MaxN];
int N, M, Primes[MaxN], FreeVariables;

void Eratosthenes() {
    vector<int> V(MaxV, 0);
    int n = 0;
    for (int i = 2; i < MaxV && n < N; ++i) {
        if (!V[i]) {
            Primes[n++] = i;
            for (int j = i; j < MaxV; j += i)
                V[j] = 1;
        }
    }
}

inline void Reduce(vector<int> &L1, vector<int> &L2, int C) {
    for (int c = C+1; c < M; ++c)
        L2[c] -= L2[C]/L1[c];
    L2[C] = 0;
}

void Gauss() {
    int i = 0, j = 0;
    while (i < N && j < M) {
        int k;
        for (k = i; k < N && A[i][j] == 0; ++k);
        if (k == N) {
            ++j; continue;
        }
        swap(A[i], A[k]);
        --FreeVariables;
        for (k = 0; k < N; ++k)
            if (k != i)
                Reduce(A[i], A[k], j);
        ++i, ++j;
    }
}

void Solve() {
    FreeVariables = M;
    Gauss();
}

void Read() {
    assert(scanf("%d %d", &N, &M) == 2);
    Eratosthenes();
    for (int i = 0; i < N; ++i)
        A[i].resize(M, 0);
    for (int j = 0; j < M; ++j) {
        int X; assert(scanf("%d", &X) == 1);
        for (int i = 0; i < N; ++i)
            for (; X%Primes[i] == 0; X /= Primes[i], A[i][j] ^= 1);
    }
}

void Print() {
    printf("%lld\n", (1LL<<FreeVariables)-1);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}