#include <stdio.h>
#include <assert.h>
#define KMax 32

typedef long long ll;
const char IN[]="light2.in",OUT[]="light2.out";

ll N,K,R;
ll P[KMax];
ll C[KMax][KMax];
int a[KMax];
bool b[KMax];

ll gcd(ll a,ll b)
{
	ll r;
	while (b)
		b=(r=a%b,a=b,r);
	assert(a!=0);
	return a;
}

void solve(int x,int ct,ll mult)
{
	if (x>K) return;
	
	if (b[x-1])
	{
		if (ct&1)
			R+= N/mult * P[ct];
		else
			R-= N/mult * P[ct];
	}
	
	if (x==K) return;
	
	b[x]=0; solve( x+1 , ct   , mult );
	b[x]=1; solve( x+1 , ct+1 , mult*a[x]/gcd(mult,a[x]));
	b[x]=0;
}

int main()
{
	int i,j;
	assert(freopen(IN,"r",stdin));
	assert(scanf("%lld%lld",&N,&K)==2);
	for (i=0;i<K;++i) assert(scanf("%d",a+i)==1);
	fclose(stdin);
	
	C[0][0]=1;
	for (i=1;i<=K;++i)
	{
		C[i][0]=1;
		for (j=1;j<=i;++j)
			C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	
	for (i=1;i<=K;++i)
		for (j=1;j<=i;j+=2)
			P[i]+=C[i][j];
	
	solve( 1 , 0 , 1);
	b[0]=1; solve( 1 , 1 , 1LL* a[0] );
	
	assert(freopen(OUT,"w",stdout));
	printf("%lld\n",R);
	fclose(stdout);
	return 0;
}