최대공약수가 뭔데

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

요약

서로 다른 N개의 자연수에서 최대공약수가 1인 K개 부분집합의 개수를 10^9+7로 나눈 나머지로 구한다.

문제

채완이는 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)$ 로 나눈 나머지를 출력하라.