Troller dreams of going to the Lolympics to represent his newly formed country, Byteland. A new game has come up at the Lolympics, and Troller believes he has the skills to win a Gold for his country.

Let's learn the rules of the game. You are given N numbers : \(A_1,A_2 ... A_N\). Troller and his opponent take alternating turns, starting with Troller's turn. In every turn, one has to choose one of the N numbers and reduce it to one of it's divisors. For example, if a number is 6, then you can reduce it to 1,2 or 3 in a single step. It's easy to see that you can't reduce 1 to anything.

Troller is smart, and hence knows beforehand if he is going to win or not if the game is played optimally. Hence, he's more interested in knowing how many non empty subsets of the N numbers leads him to a victory if the game is played optimally on the chosen subset. Help him with this problem, while he prepares for Gold!

Input Format:
The first line contains N, the count of numbers. The next line contains N space separated integers \(A_1, A_2, A_3 ... A_N\).

Output Format:
Output consists of one integer, the number of ways you can choose a non-empty subset such that you win the game if played optimally. Since this integer can be very big, output it modulo \(10^9\) + 7.

Constraints:
\(1 \le N \le 500\)
\(1 \le Ai \le 10^{15}\)