407929: GYM102944 F Flint
Description
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.
InputThe 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.
OutputOutput the number of comprehensive subsets. Since this number may be large, output this number modulo $$$10^9+7$$$.
ExamplesInput3 6 10 15Output
1Input
5 2 4 6 8 10Output
0Input
5 2 3 5 7 11Output
26