23260번 - 최대공약수가 뭔데

문제

채완이는 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$

힌트