B"Let's call a non-empty sequence of positive integers a1, xe2 x80 x89a2... ak coprime if the greatest common divisor of all elements of this sequence is equal to 1. Given an array a consisting of n positive integers, find the number of its coprime subsequences. Since the answer may be very large, print it modulo 109 xe2 x80 x89+ xe2 x80 x897. Note that two subsequences are considered different if chosen indices are different. For example, in the array [1, xe2 x80 x891] there are 3 different subsequences: [1], [1] and [1, xe2 x80 x891]. The first line contains one integer number n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89100000). The second line contains n integer numbers a1, xe2 x80 x89a2... an (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ai xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89100000). Print the number of coprime subsequences of a modulo 109 xe2 x80 x89+ xe2 x80 x897. In the first example coprime subsequences are: In the second example all subsequences are coprime. "...