{"raw_statement":[{"iden":"statement","content":"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.\n\nGiven 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 + 7.\n\nNote 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\\]."},{"iden":"input","content":"The first line contains one integer number _n_ (1 ≤ _n_ ≤ 100000).\n\nThe second line contains _n_ integer numbers _a_1, _a_2... _a__n_ (1 ≤ _a__i_ ≤ 100000)."},{"iden":"output","content":"Print the number of _coprime_ subsequences of _a_ modulo 109 + 7."},{"iden":"examples","content":"Input\n\n3\n1 2 3\n\nOutput\n\n5\n\nInput\n\n4\n1 1 1 1\n\nOutput\n\n15\n\nInput\n\n7\n1 3 5 15 3 105 35\n\nOutput\n\n100"},{"iden":"note","content":"In the first example _coprime_ subsequences are:\n\n1.  1\n2.  1, 2\n3.  1, 3\n4.  1, 2, 3\n5.  2, 3\n\nIn the second example all subsequences are _coprime_."}],"translated_statement":[{"iden":"statement","content":"我们称一个非空正整数序列 #cf_span[a1, a2... ak] 为 _互质_ 的，当且仅当该序列所有元素的最大公约数等于 #cf_span[1]。\n\n给定一个包含 #cf_span[n] 个正整数的数组 #cf_span[a]，求其 _互质_ 子序列的数量。由于答案可能很大，请对 #cf_span[109 + 7] 取模输出。\n\n注意，如果所选下标不同，则两个子序列被视为不同。例如，在数组 #cf_span[[1, 1]] 中，有 #cf_span[3] 个不同的子序列：#cf_span[[1]]、#cf_span[[1]] 和 #cf_span[[1, 1]]。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2... an]（#cf_span[1 ≤ ai ≤ 100000]）。\n\n请输出数组 #cf_span[a] 的 _互质_ 子序列数量对 #cf_span[109 + 7] 取模的结果。\n\n在第一个例子中，_互质_ 子序列为：\n\n在第二个例子中，所有子序列都是 _互质_ 的。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2... an]（#cf_span[1 ≤ ai ≤ 100000]）。"},{"iden":"output","content":"请输出数组 #cf_span[a] 的 _互质_ 子序列数量对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入31 2 3输出5输入41 1 1 1输出15输入71 3 5 15 3 105 35输出100"},{"iden":"note","content":"在第一个例子中，_互质_ 子序列为：   #cf_span[1]  #cf_span[1, 2]  #cf_span[1, 3]  #cf_span[1, 2, 3]  #cf_span[2, 3] 在第二个例子中，所有子序列都是 _互质_ 的。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers with $ 1 \\leq a_i \\leq 10^5 $.  \nA subsequence $ S \\subseteq A $ is *coprime* if $ \\gcd(S) = 1 $.  \nLet $ \\mathcal{S} $ denote the set of all non-empty subsequences of $ A $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nCompute the number of coprime non-empty subsequences:  \n$$\n\\left| \\left\\{ S \\subseteq A \\mid S \\neq \\emptyset,\\ \\gcd(S) = 1 \\right\\} \\right| \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}