如果正整数 a1, a2...ak 的非空序列所有元素的最大公约数等于 1,则该序列称为互质。
给定一个由 n 个正整数组成的数组 a,找到其互质子序列的数量。由于答案可能非常大,因此将其打印为 109 + 7 模。
请注意,如果选择的索引不同,则两个子序列被视为不同。例如,数组 [1, 1] 中有 3 个不同的子序列:[1]、[1] 和 [1, 1]。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100000)。
第二行包含n个整数a1, a2... an (1 ≤ ai ≤ 100000)。
输出
打印模 109 + 7 的互质子序列的数量。
示例
输入 #1
3 1 2 3
输出 #1
5
输入 #2
4 1 1 1 1
输出 #2
15
输入 #3
7 1 3 5 15 3 105 35
输出 #3
100
注意
在第一个示例中,互质子序列是:
1. 1
2. 1, 2
3. 1, 3
4. 1, 2, 3
5. 2, 3
在第二个示例中,所有子序列都是互质的。