CF803F Coprime Subsequences

Let's call a non-empty sequence of positive integers $ a_{1},a_{2}...\ a_{k} $ 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 $ 10^{9}+7 $ . Note that two subsequences are considered different if chosen indices are different. For example, in the array $ [1,1] $ there are $ 3 $ different subsequences: $ [1] $ , $ [1] $ and $ [1,1] $ .

N/A

N/A

In the first example coprime subsequences are: 1. $ 1 $ 2. $ 1,2 $ 3. $ 1,3 $ 4. $ 1,2,3 $ 5. $ 2,3 $ In the second example all subsequences are coprime.