11910번 - 경비원

상수는 어제 석환이로부터 거대한 저택을 매입했습니다. 상수는 이 저택을 지키는 경비원들이 필요하다고 생각하여 모집 공고를 올렸고, 그 결과 n명이 지원했습니다. 상수는 편의상 이들에게 1 이상 n 이하의 번호를 붙였습니다.

i (1≤i≤n)번 경비원에게는 가장 좋아하는 수 a_i가 있습니다. 이 값은 항상 양의 정수입니다. 상수는 i번 경비원과 j번 경비원이 같이 경비를 설 때, a_i와 a_j의 최대공약수가 2 이상이면, 서로 친밀감을 느껴서 대화하느라 경비를 제대로 서지 않는다고 생각합니다.

따라서 상수는 경비원들을 2명 이상 고용하되, 이들 중 두 명을 어떻게 골라도 좋아하는 수의 최대공약수가 1이 되도록 하려고 합니다. 이를 위해 상수는 고용할 수 있는 모든 경우의 수를 따져보고자 합니다. 상수를 도와주세요.

첫 번째 줄에 n (2 ≤ n ≤ 2,222)이 주어집니다. 두 번째 줄에 a₁,a₂,⋯,a_n (a_i ≤ 2,222)이 공백을 사이로 두고 차례대로 주어집니다.

첫 번째 줄에 상수가 경비원들을 고용할 수 있는 모든 경우의 수를 1,000,000,007 (=109+7)로 나눈 나머지를 출력합니다.

예제 1에서 가능한 경우는 아래와 같습니다.

• {1, 2}
• {1, 3}
• {1, 4}
• {2, 3}
• {3, 4}
• {1, 2, 3}
• {1, 3, 4}