题目描述

一年前，$Leha$ 在公园的长凳上发现了一个由 $n$ 个数字组成的数组。$Leha$ 认为，如果在所有 $1 ≤ i < n$ 的条件下，$a_{p_i} * a_{p_{i + 1}}$ 不是完全平方数，那么排列 $p$ 就是正确的。$Leha$ 想找出 $10^9 + 7$ 模的正确排列数。

输入格式

第一行输入数据包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_1, a_2, ... , a_n$，表示数组中的每个元素。

输出格式

输出一个整数，表示正确的排列数量对 $10^9 + 7$ 取模的结果。

样例

3
1 2 4

2

7
5 2 4 2 4 1 1

144

提示

样例1解释

样例1

[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 不是完全平方。

数据范围

$1 \le n \le 300$，$1 \le a_i \le 10^9$