Juliany is a young programmer in love with math. And as such, it has your favorite numbers. She loves perfect squares, is completely fascinated by them and their gorgeous properties. So she invents several games and hobbies related to them.

One of the games Juliany invented was the insane "So Many Squares" which she plays every day in the intervals of job with her colleague Felipe. The game consists of Felipe choosing N natural numbers, and from these numbers, Juliany has to say how many different ways she can choose some, or possibly all, of these numbers in such a way that their multiplication is a perfect square. Obviously the job of thinking about so many numbers and still wondering if your colleague's answer is correct is not as exciting for Felipe as for Juliany. For this reason and to facilitate his work, he simply chooses a small group of prime numbers, at most 50, and generates the N numbers for the game from those primes. The generated numbers have only prime factors belonging to this group.

Your task is to help Felipe. Since he has already generated the numbers, you should make a program that checks whether Juliany's answer is correct. Since this can be a very large number, your answer should be only the modulo of that number by 10⁹ + 7.

Input

The input is composed of several test cases. The first line of a test case contains an integer N (1 ≤ N ≤ 10⁴) as described above. The next line contains N integers Ai (1 ≤ Ai ≤ 10⁶) representing the numbers generated by Felipe. The input ends when N = 0.

Output

The output consists of one line per test case containing a single integer representing the Juliany's answer modulo 10⁹ + 7.

Example

Input:
3
2 4 8
4
14 15 35 7
5
6 42 105 63 20
0

Output:
3
0
1