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-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 05:36:32 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|