Problem Description

Rabbit is currently in Division $ 2 $ of a programming contest and is struggling to advance to Division $ 1 $.

Therefore, Rabbit holds a grudge against dividing integers by $ 2 $.

Meanwhile, Rabbit has written numbers from $ 1 $ to $ n $ on a blackboard and is about to perform the following operation $ q $ times:

• During the $ i $-th operation, if there are numbers on the blackboard that are divisible by $ a_i $, divide those numbers by $ a_i $ once.

How many $ 1 $s will be left on the blackboard eventually?

Input Format

The input is given from the standard input in the following format:

$ n $ $ q $ $ a_1 $ $ : $ $ a_q $

• The first line contains the number of numbers to write on the blackboard $ n $ and the number of operations $ q $, separated by spaces.
• From the second line, $ q $ lines follow, each giving $ a_i $, which represents the number to divide by in the $ i $-th operation.

Output Format

Output should follow the standard output in the following format:

• Output the number of $ 1 $s left on the blackboard in one line.

Sample Input and Output

Sample Input #1

7 2
3
6

Sample Output #1

2

Sample Input #2

7 2
6
3

Sample Output #2

3

Notes/Hints

Constraints

• $ 1 $ ≦ $ n $ ≦ $ {10}^{13} $
• $ 1 $ ≦ $ q $ ≦ $ 24 $
• $ 3 $ ≦ $ a_i $ ≦ $ 50 $

Subtasks

Subtask $ 1 $ \[ $ 25 $ points \]

• Satisfies $ 1≦n≦10^6 $.

Subtask $ 2 $ \[ $ 75 $ points \]

• No additional constraints.

Sample Explanation 1

The numbers change as follows: 1 2 3 4 5 6 7 Divided by 3 1 2 1 4 5 2 7 Divided by 6 1 2 1 4 5 2 7 Therefore, in the cases of $ 1, 3 $, there are $ 2 $ $ 1 $s left eventually.

Sample Explanation 2

The numbers change as follows: 1 2 3 4 5 6 7 Divided by 6 1 2 3 4 5 1 7 Divided by 3 1 2 1 4 5 1 7 Therefore, in the cases of $ 1, 3, 6 $, there are $ 3 $ $ 1 $s left eventually.

见题面 Input 部分

见题面 Output 部分