F. Flint
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You were assuming Flint, Michigan. Fooled you! This problem is about a middle school teacher named Mr. Flint. One day, Mr. Flint created a new number theory game for his students. He prepared a set of $$$N$$$ integers. Then, Mr. Flint asked the students, one-by-one, to choose a non-empty subset of those integers and compute the greatest common divisor of that subset. If the value is $$$1$$$, then the subset is called a "comprehensive" subset and the student receives a point. Students may not choose a previously chosen subset.

To make sure that every student has an opportunity to receive a point, Mr. Flint comes to you, because you were his favorite student years ago and he has heard that you are good at computing. He asks you to compute the number of comprehensive subsets. He hopes this number is at least the size of the class.

Input

The first line contains an integer $$$N$$$ ($$$1\le N\le 100$$$). The next line contains the $$$N$$$ positive integers $$$a_1, a_2, \ldots, a_N$$$. ($$$1\le a_i\le 10^9$$$) that Mr. Flint chose.

Output

Output the number of comprehensive subsets. Since this number may be large, output this number modulo $$$10^9+7$$$.

Examples
Input
3
6 10 15
Output
1
Input
5
2 4 6 8 10
Output
0
Input
5
2 3 5 7 11
Output
26