Problem Description

Xiao X has received 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 find out the answer.

Input Format

The first line contains two positive integers \( n \) and \( |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 \).

Data Range:

• \( 3 \le n \le 10^9 \).
• \( 3 \le |S| \le 20 \).
• All elements in \( S \) are guaranteed to be less than \( n \), and they may not be distinct.

Output Format

A single line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

10 3
2 4 5

Sample Output #1

1

Sample Input #2

100000 6
14 47 31 233 666 59

Sample Output #2

91

Notes

Sample 1 Explanation:

Only when \( x = 6 \):

• \( x \equiv 0 \pmod{2} \)
• \( x \equiv 1 \pmod{5} \)
• \( x \equiv 2 \pmod{4} \)

These conditions are satisfied.

见题面 Input 部分

见题面 Output 部分