GCD Subset Challenge

In the ancient Kingdom of Rhun, mathematicians believed that numbers possessed magical properties when combined in the right way. During the annual Festival of Numbers, villagers are challenged to create groups from a given set of mystical integers. The challenge is to form a non-empty subset of these integers such that the greatest common divisor (GCD) of the subset equals $1$. Only those groups with $\gcd=1$ are said to invoke the ancient magic.

Your task is to help the villagers determine the number of ways to choose a non-empty subset from the given array of integers such that the GCD of all the numbers in that subset is exactly $1$. Since the number of possible subsets can be huge, report the answer modulo $10^9+7$.

Input Format

• The first line contains a single integer $n$ ($1 \leq n \leq 10^5$), representing the number of integers.
• The second line contains $n$ space-separated positive integers $a_1, a_2, \dots, a_n$ where each $a_i$ satisfies $1 \leq a_i \leq 10^5$.

Output Format

• Output a single integer representing the number of non-empty subsets with $\gcd=1$, taken modulo $10^9+7$.

Examples

Input

3
1 2 3

Output

5

Input

4
2 4 8 16

Output

0