어느 수인가

시간 제한1초메모리 제한1024 MB

요약

주어진 소수들의 배수가 아닌 양의 정수 중 n번째 수를 구합니다.

난이도: 보통10점 중 6점
유형: 이분 탐색, 정수론, 조합론
정답자: 아직 제출이 없습니다

문제

나타샤는 수를 세는 것을 좋아한다. 하지만 어떤 소수 집합은 불운을 부른다는 이야기를 들었다. 그래서 그 소수들과 그 소수들의 배수를 모두 건너뛰고 센다. 예를 들어 나타샤가 피하는 소수가 3, 5, 11이면, 세기 시작할 때 다음 정수를 말하게 된다:

1, 2, 4, 7, 8, 13, 14, 16, 17, 19, 23, …

입력

첫 줄에 두 정수 n (1 ≤ n ≤ $10^{17}$ )과 k (1 ≤ k ≤ 14)가 주어진다. n은 질의 번호이고, k는 나타샤가 세는 동안 피하는 서로 다른 소수의 개수이다. 둘째 줄에는 피해야 할 k개의 서로 다른 소수가 어떤 순서로든 주어진다. 이 소수들의 배수도 함께 건너뛴다. 소수들의 곱은 $10^{17}$ 을 넘지 않는다. 예를 들어 $\{2, 3, 5, 11\}$ 은 곱이 330이라 가능하지만, $\{1000000007, 1000000009\}$ 는 곱이 $10^{17}$ 을 넘어서 주어질 수 없다.

출력

나타샤가 말하는 n번째 수를 출력한다.

예제2

예제 1
입력
```
11 3
3 5 11
```
예상 출력
```
23
```
예제 2
입력
```
9 4
2 7 3 5
```
예상 출력
```
37
```