12944번 - 재미있는 숫자 놀이

문제

민호는 K개의 카드를 가지고 있는데 각각의 카드에는 양의 정수가 적혀 있다. 이 카드들을 너무 좋아하는 민호는 이것들을 이용해 재미있는 놀이를 생각해 냈다.

1이상 N이하의 양의 정수 중에서 민호가 가지고 있는 카드들 중 적어도 한개로 나눠떨어지는 숫자는 몇개인지 알아보는 것이다.

하지만 경우의 수가 너무 많아 손으로 셀 수 없다는 것을 깨달은 민호는 여러분들에게 도움을 요청했다. 민호를 도와 민호가 놀이를 성공적으로 마칠 수 있게 해주자.

입력

첫 번째 줄에 N, K (1 ≤ N ≤ 10⁹, 1 ≤ K ≤ 20) 이 공백을 구분으로 주어진다.

다음 줄에는 민호가 가지고 있는 K개의 카드에 적힌 숫자가 A_i (1 ≤ i ≤ N, 1 ≤ A_i ≤ 10⁹)가 공백을 구분으로 차례대로 주어진다.

출력

1이상 N이하의 양의 정수 중 민호가 가지고 있는 카드들 중 적어도 한 개로 나눠떨어지는 수의 개수를 출력한다.

제한

힌트