Diofanto de Alexandria foi um importante (se não o mais) algebrista grego. Ele escreveu sobre um tipo especial de equações chamadas equações diofantinas, dentre essas equações, vamos considerar somente as da forma somatório( AiXi ) = 1, onde Xi são variáveis independentes.
Para que haja solução inteira, o máximo divisor comum entre os coeficientes Ai deve ser igual a 1.
Dado um conjunto de N números, você pode escolher um subconjunto de tamanho K para ser os coeficientes de sua equação. De quantas formas você pode escolher esse subconjunto de forma que exista solução inteira?
A primeira linha da entrada tem os números N (1 <= N <= 1000) e K (1 <= K <= 6). As N linhas seguinte descrevem o conjunto, cada uma com um número distinto entre 1 e 1000.
Imprima o número de formas de escolher um subconjunto de K elementos de forma que o MDC entre eles seja 1.
No primeiro caso {1,3,4,6,9}, K = 2, os subconjuntos com MDC = 1 são: {1,3}, {1,4}, {1,6}, {1,9}, {3,4} e {4,9}