B"Winter is here at the North and the White Walkers are close. John Snow has an army consisting of n soldiers. While the rest of the world is fighting for the Iron Throne, he is going to get ready for the attack of the White Walkers. He has created a method to know how strong his army is. Let the i-th soldier xe2 x80 x99s strength be ai. For some k he calls i1, xe2 x80 x89i2, xe2 x80 x89..., xe2 x80 x89ik a clan if i1 xe2 x80 x89< xe2 x80 x89i2 xe2 x80 x89< xe2 x80 x89i3 xe2 x80 x89< xe2 x80 x89... xe2 x80 x89< xe2 x80 x89ik and gcd(ai1, xe2 x80 x89ai2, xe2 x80 x89..., xe2 x80 x89aik) xe2 x80 x89> xe2 x80 x891 . He calls the strength of that clan k xc2 xb7gcd(ai1, xe2 x80 x89ai2, xe2 x80 x89..., xe2 x80 x89aik). Then he defines the strength of his army by the sum of strengths of all possible clans. Your task is to find the strength of his army. As the number may be very large, you have to print it modulo 1000000007 (109 xe2 x80 x89+ xe2 x80 x897). Greatest common divisor (gcd) of a sequence of integers is the maximum possible integer so that each element of the sequence is divisible by it. The first line contains integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89200000) -- the size of the army. The second line contains n integers a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89an (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x891000000) -- denoting the strengths of his soldiers. Print one integer -- the strength of John Snow's army modulo 1000000007 (109 xe2 x80 x89+ xe2 x80 x897). In the first sample the clans are {1}, xe2 x80 x89{2}, xe2 x80 x89{1, xe2 x80 x892} so the answer will be 1 xc2 xb73 xe2 x80 x89+ xe2 x80 x891 xc2 xb73 xe2 x80 x89+ xe2 x80 x892 xc2 xb73 xe2 x80 x89= xe2 x80 x8912 "...