Coprime Subsequences

양의 정수로 이루어진 비어 있지 않은 수열 a1, a2... ak의 모든 원소의 최대공약수가 1이면 이 수열을 서로소라고 부른다.

n개의 양의 정수로 이루어진 배열 a가 주어질 때, 그 부분 수열 중 서로소인 것의 개수를 구한다. 답이 매우 클 수 있으므로 109 + 7로 나눈 나머지를 출력한다.

선택한 인덱스가 서로 다르면 두 부분 수열은 서로 다른 것으로 간주한다. 예를 들어 배열 $[1, 1]$에는 $[1]$, $[1]$, $[1, 1]$의 서로 다른 부분 수열 3개가 있다.

첫 번째 줄에는 정수 하나 n (1 ≤ n ≤ 100000)이 주어진다.

두 번째 줄에는 n개의 정수 a1, a2... an (1 ≤ ai ≤ 100000)이 주어진다.

a의 서로소 부분 수열의 개수를 109 + 7로 나눈 나머지를 출력한다.

첫 번째 예제에서 서로소 부분 수열은 다음과 같다.

1. 1
2. 1, 2
3. 1, 3
4. 1, 2, 3
5. 2, 3

두 번째 예제에서는 모든 부분 수열이 서로소이다.