Hi, I have a small problem that has been bothering me for a while.

Heres the problem: You're given an array which contains N integers (N <=2*1e5). Your task is to print out the sum of GCD of all 2^n-1 (pow(2,n)-1 for clear statement) subsequence. The definition of an subsquence is a set of index i1, i2, i3, ..., ik that i1<i2<i3<...<ik. You have to moduluo the answer by 1e9+7 otherwise is gonna be overflowed, also a[i] <=1e6 and N <=2*1e5.

A sample test case is:

input: 3 1 2 3

output: 10

input: 5 3 6 9 5 10 output: 72