겨울이 왔다

겨울이 왔고 North and the White Walkers이(가) 가까이 있다. John Snow에게는 n명의 병사로 이루어진 군대가 있다. 나머지 세계가 Iron Throne을(를) 차지하기 위해 싸우는 동안, 그는 White Walkers의 공격에 대비하려 한다.

그는 자신의 군대가 얼마나 강한지 알아내는 방법을 만들었다. i-th 병사의 힘을 ai라고 하자. 어떤 k에 대해, i1 < i2 < i3 < ... < ik이고 gcd(ai1, ai2, ..., aik) > 1이면 그는 i1, i2, ..., ik을(를) 하나의 부족이라고 부른다. 그는 그 부족의 힘을 k·gcd(ai1, ai2, ..., aik)로 정의한다. 그런 다음 가능한 모든 부족의 힘을 합한 값을 자신의 군대의 힘으로 정의한다.

군대의 힘을 구해야 한다. 그 수는 매우 클 수 있으므로 1000000007 (109 + 7)로 나눈 나머지를 출력해야 한다.

정수 수열의 최대공약수(gcd)는 수열의 각 원소가 모두 그 수로 나누어떨어지게 하는 정수 중 가능한 최댓값이다.

첫째 줄에는 군대의 규모를 나타내는 정수 n (1 ≤ n ≤ 200000)이(가) 주어진다.

둘째 줄에는 병사들의 힘을 나타내는 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ 1000000)이 주어진다.

John Snow's 군대의 힘을 1000000007 (109 + 7)로 나눈 나머지를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 부족은 {1}, {2}, {1, 2}이므로 답은 1·3 + 1·3 + 2·3 = 12이다.