Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. On the Bench

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA year ago on the bench in public park Leha found an array of *n* numbers. Leha believes that permutation *p* is right if for all 1 ≤ *i* < *n* condition, that *a*_{pi}·*a*_{pi + 1} is not perfect square, holds. Leha wants to find number of right permutations modulo 10^{9} + 7.

Input

First line of input data contains single integer *n* (1 ≤ *n* ≤ 300) — length of the array.

Next line contains *n* integers *a*_{1}, *a*_{2}, ... , *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) — found array.

Output

Output single integer — number of right permutations modulo 10^{9} + 7.

Examples

Input

3

1 2 4

Output

2

Input

7

5 2 4 2 4 1 1

Output

144

Note

For first example:

[1, 2, 4] — right permutation, because 2 and 8 are not perfect squares.

[1, 4, 2] — wrong permutation, because 4 is square of 2.

[2, 1, 4] — wrong permutation, because 4 is square of 2.

[2, 4, 1] — wrong permutation, because 4 is square of 2.

[4, 1, 2] — wrong permutation, because 4 is square of 2.

[4, 2, 1] — right permutation, because 8 and 2 are not perfect squares.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2017 01:23:39 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|