시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 32 MB 16 7 6 40.000%

문제

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

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

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

입력

첫 번째 줄에 n (2 ≤ n ≤ 2,222)이 주어집니다. 두 번째 줄에 a1,a2,⋯,an (ai ≤ 2,222)이 공백을 사이로 두고 차례대로 주어집니다.

 

출력

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

 

예제 입력

4
1 2 3 4

예제 출력

7

예제 입력 2

5
10 12 14 16 18

예제 출력 2

0

예제 입력 3

44
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

예제 출력 3

900563

예제 입력 4

5
3 21 7 45 15

예제 출력 4

3

예제 입력 5

3
3 2 3

예제 출력 5

2

힌트

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

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