题目描述

给定一个序列 $a(a_i\le 10^9)$，长度为 $n(n\le 300)$。

试求有多少 $1$ 到 $n$ 的排列 $p_i$，满足对于任意的 $2\le i\le n$ 有 $a_{p_{i-1}}\times a_{p_i}$ 不为完全平方数，答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

输出格式

一个整数表示答案，对 $10^9+7$ 取模。

3
1 2 4

2

7
5 2 4 2 4 1 1

144