Xsquare is not good at Mathematics, but his Mathematics teacher considers him the most brilliant student of the class. How come ? Actually Xsquare was the only one to complete the Mathematics Assignment given by his maths teacher by solving a very hard problem.

Lets first describe the problem given in the Xsquare's Assignment .

Given an integer X where (X ≤ 10^10) . Count the number of ways of representing integer X as sum of two Squares? Easy one , Isn't it ?

Xsquare tried hard and finally solved this problem.

Now, his Mathematics teacher thinks that Xsquare can solve the same problem with higher constaints, say for X=10^1000. On the Other hand his mathematics teacher also knows that Xsquare is frightened of very big numbers. So, he decided to represent the number X as the product of N numbers.

Xsquare knows that he cannot solve this problem with huge constraints. But on the same side, he does not want to disappoint his Mathematics teacher. So, he asked you for help.

Your task is very very simple : Given N numbers, you need to tell the number of ways of representing the product of these N numbers as sum of two squares.

Look at the sample test case for better understanding of the problem.

INPUT:

First line of input contains a single integer N denoting the number of numbers. Next line of input contains N space separated integers denoting the values of N numbers.

OUTPUT:

Output the number of ways of representing the given number X as sum of two squares, Where X = Product of given N numbers.

NOTE

Number of ways of representing a number X as sum of two squares can be very large. so output the answer mod 10^9+7.

CONSTRAINTS:

1 ≤ N ≤ 200

1 ≤ X ≤ 10^2000

None of the N numbers exceeds 10^10.

SAMPLE INPUT
3
2 1 2

SAMPLE OUTPUT
4

Explanation

Explanation:

212=4

There are 4 ways of representing 4 as sum of two squares.

0^2 + 2^2 = 4
0^2 + (-2)^2 = 4
2^2 + 0^2 = 4
(-2)^2 + 0^2 = 4

Look at the explanation of the sample test case and notice that the sign as well as order matters.

见题面

见题面