경비원 Batch 컴파일 명령

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

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

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

입력 형식

첫 번째 줄에 $n$이 주어집니다. 두 번째 줄에 $a_{1}, a_{2}, \cdots, a_{n}$이 공백을 사이로 두고 차례대로 주어집니다.

출력 형식

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

부분문제

예제

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

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

각 경비원들이 가장 좋아하는 수가 모두 짝수이기 때문에 고용할 수 있는 경우가 없습니다.