#include <fstream>
#include <queue>

using namespace std;

typedef long long int64;

int64 N, K;
int D[24];
int64 result;
int64 Comb[24][24], C[24][24];
char nrb[1 << 22];
bool aux[1 << 22];
queue<int> Q1;
queue<int64> Q2;

inline int64 cmmdc(int64 a, int64 b)
{
	if (b == 0) return a;
	return cmmdc(b, a % b);
}

int main()
{
	ifstream fin("light2.in");
	ofstream fout("light2.out");
	
	for (int i = 1; i < (1 << 22); ++i)
		nrb[i] = nrb[i & (i - 1)] + 1;
	
	Comb[0][0] = 1;
	for (int i = 1; i <= 22; ++i)
	{
		Comb[i][0] = 1;
		for (int j = 1; j <= i; ++j)
		{
			Comb[i][j] = Comb[i - 1][j] + Comb[i - 1][j - 1];
			C[i][j] = C[i][j - 1] + Comb[i][j] * (-C[j][j - 1] + j % 2);
		}
	}
	
	fin >> N >> K;
	for (int i = 1; i <= K; ++i)
		fin >> D[i];
	
	Q1.push(0); Q2.push(1);
	while (!Q1.empty())
	{
		int now = Q1.front();
		int64 val = Q2.front();
		Q1.pop(), Q2.pop();
		
		for (int i = 0; i < K; ++i)
			if (!(now & (1 << i)) && !aux[now | (1 << i)])
			{
				int64 valnow = val;
				valnow = valnow / cmmdc(valnow, D[i + 1]) * D[i + 1];
				if (valnow > N) continue;
				
				aux[now | (1 << i)] = true;
				Q1.push(now | (1 << i));
				Q2.push(valnow);
				
				result += (-C[nrb[now] + 1][nrb[now]] + (nrb[now] + 1) % 2) * (N / valnow);
			}
	}
	
	fout << result;
	
	fin.close();
	fout.close();
}