Marks :20

: 29 | : 1

Carl is bored of playing with ordinary prime numbers. Thus, he comes up with some special numbers called Omega Primes.

A number $$$X$$$ is called Omega Prime, if there exists no perfect square $$$Y (Y > 1)$$$ such that $$$Y$$$ divides $$$X$$$.

For example, 6 is an Omega Prime because there is no perfect square except 1 that divides 6.

On the other hand, 12 is not an Omega Prime as 4 (which is a perfect square) is a divisor of 12.

Carl decides to play a bit more with Omega Primes. He has an array $$$A$$$ of integers. Carl wants to find the number of different subsets such that the product of elements for each subset, results in an Omega Prime. Help Carl find this number.

Since this number can be large, output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$1\le n \le 20000$$$ denoting size of array $$$A$$$

The second line contains $$$n$$$ space separated integers, where $$$1\le i_{th} \le n $$$ integer denotes $$$1\le A[i] \le 30$$$

Output

Output the answer as described in statement.

Examples

Input

3 2 4 3

Output

3

Input

3 2 2 2

Output

3

Input

6 2 30 15 18 24 22

Output

6

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

But to **Run** or **Submit** the Problem, you need to Log In.

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Do let us know your issue.