Migrated from Lutece 1156 Dividing Numbers

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given an integer $N$ ($1 \leq N \leq 10^{13}$) and $K$ ($1 \leq K \leq 100$) co-prime numbers $P_1，P_2，...，P_k$, which are less than 1000. Please tell me how many integers in range $[1,N]$ satisfied that none of a number in $P_1，P_2，...，P_k$ can divide it.

Input

The first line contains two integers $N$ ($1 \leq N \leq 10^{13}$) and $K$ ($1 \leq K \leq 100$).

The second line contains $K$ numbers $P_1，P_2，...，P_k$. It is guaranteed that $2 \leq P_i \leq 1000$.

It is guaranteed that the given $K$ numbers are pairwise co-prime.

Output

Output an integer representing the number of integers in range $[1,N]$ satisfied the condition.

Samples

20 3
2 3 5

6

50 2
15 8

41

Resources

2015 UESTC ACM Summer Training Team Selection (4)