CF840C.On the Bench

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 109 + 7.

一年前，Leha 在公园的长椅上发现了一个包含 $n$ 个数字的数组。Leha 认为一个排列 $p$ 是“合法的”，当且仅当对所有 $1 \le i < n$，均满足 $a_{p_i} \cdot a_{p_{i+1}}$ 不是一个完全平方数。Leha 想要求出合法排列的个数，并对 $10^9 + 7$ 取模。

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 ≤ 109) — found array.

输入数据的第一行包含一个整数 $n$（$1 \leq n \leq 300$）—— 数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）—— 所给定的数组。

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

输出一个整数——满足条件的排列数目对 $10^9 + 7$ 取模的结果。

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.

第一个例子：

[1, 2, 4] — 正确的排列，因为 2 和 8 都不是完全平方数。

[1, 4, 2] — 错误的排列，因为 4 是 2 的平方。

[2, 1, 4] — 错误的排列，因为 4 是 2 的平方。

[2, 4, 1] — 错误的排列，因为 4 是 2 的平方。

[4, 1, 2] — 错误的排列，因为 4 是 2 的平方。

[4, 2, 1] — 正确的排列，因为 8 和 2 都不是完全平方数。