경비원

상수는 어제 거대한 저택을 샀다. 저택을 지킬 경비원을 모집했더니 n명이 지원했고, 상수는 지원자에게 1번부터 n번까지 번호를 붙였다.

i번 지원자에게는 가장 좋아하는 수 $a_i$가 있다. 이 수는 양의 정수다. 두 지원자 i와 j가 같이 경비를 설 때 $a_i$와 $a_j$의 최대공약수가 2 이상이면, 둘은 친밀감을 느껴 대화하느라 경비를 제대로 서지 않는다.

상수는 지원자 중 2명 이상을 뽑되, 뽑힌 사람 가운데 어느 두 명을 골라도 좋아하는 수의 최대공약수가 1이 되도록 하려고 한다. 뽑는 방법이 몇 가지인지 구하라. 뽑힌 번호의 집합이 다르면 서로 다른 방법이다. 좋아하는 수가 같은 두 지원자는 서로 다른 사람이지만, 최대공약수가 그 수와 같아 2 이상이므로 함께 뽑을 수 없다.

첫째 줄에 지원자 수 n이 주어진다. ($2 \le n \le 2222$)

둘째 줄에 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 차례대로 주어진다. ($1 \le a_i \le 2222$)

첫째 줄에 뽑는 방법의 수를 1,000,000,007($=10^9+7$)로 나눈 나머지를 출력한다.