On the Bench

2000ms

262144K

Description:

A 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_{p_i}·a_{p_i + 1} is not perfect square, holds. Leha wants to find number of right permutations modulo 10⁹ + 7.

Input:

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

Next line contains n integers a₁, a₂, ... , a_n (1 ≤ a_i ≤ 10⁹) — found array.

Output:

Output single integer — number of right permutations modulo 10⁹ + 7.

Sample Input:

3
1 2 4

Sample Output:

Sample Input:

7
5 2 4 2 4 1 1

Sample Output:

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.

Informação

Provedor Codeforces

Código CF840C