시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB290584141.414%

문제

채완이는 1학년 후배들이 유클리드 호제법을 배웠다는 소식을 듣고 지문에 "최대공약수"가 들어간 문제를 만들기로 했다.

오름차순으로 정렬된 길이가 $K$인 수열 $\{A_1, A_2 \dots A_K\} $의  최대공약수가 1일 때 이를 K-채완 수열이라 한다.

${A_1, A_2 \dots A_K} $의 최대공약수는 모든 $A_i (1 \leq i \leq K) $의 공통된 약수인 자연수 중 가장 큰 수를 의미한다.

서로 다른 $N$개의 자연수가 주어질 때 서로 다른 $K$개를 선택하여 K-채완 수열을 만드는 경우의 수를 구해보자.

입력

첫째 줄에 $N$, $K$가 주어진다.

둘째 줄에 $1\,000\,000$이하인 자연수 $N$개가 공백으로 구분되어 주어진다. 

출력

K-채완 수열을 만드는 경우의 수를 $1\,000\,000\,007(=10^9+7)$로 나눈 나머지를 출력하라. 

제한

  • $1 \leq N \leq 1\,000\,000$
  • $1 \leq K \leq N$

예제 입력 1

5 2
2 3 5 7 11

예제 출력 1

10

주어진 수는 모두 소수이고 따라서 어떠한 쌍을 골라도 서로소다. 그러므로 예제의 출력은 $\binom{5}{2} = 10$이다.

예제 입력 2

5 2
2 3 6 8 11

예제 출력 2

6