Problem Description

Xiao X is given a positive integer $n$ and a set of positive integers $S$. He wants to know how many positive integers $x$ satisfy all of the following conditions:

• $3 \le x \le n$
• There exists $a \in S$ such that $x \equiv 0 \pmod a$
• There exists $b \in S$ such that $x-1 \equiv 0 \pmod b$
• There exists $c \in S$ such that $x-2 \equiv 0 \pmod c$

Please help Xiao X compute the answer.

Input Format

The first line contains two positive integers $n, |S|$, representing the given $n$ and the size of the set $S$.

The second line contains $|S|$ positive integers, representing the elements in the set $S$.

Constraints:

• $3 \le n \le 10^9$.
• $3 \le |S| \le 20$.
• All elements in $S$ are less than $n$. Elements are not guaranteed to be distinct.

Output Format

Output one integer in a single line, representing the answer.

10 3
2 4 5

1

100000 6
14 47 31 233 666 59

91

Hint

[Sample $1$ Explanation]

Only when $x = 6$:

• $x \equiv 0 \pmod 2$
• $x \equiv 1 \pmod 5$
• $x \equiv 2 \pmod 4$

do the conditions hold.

Translated by ChatGPT 5