CF840C On the Bench

一年前，Leha 在公园的长椅上发现了一个长度为 $n$ 的数组。Leha 认为一个排列 $p$ 是“正确的”，当且仅当对于所有 $1 \leq i < n$，都有 $a_{p_i} \cdot a_{p_{i+1}}$ 不是一个完全平方数。Leha 想要计算满足条件的“正确”排列的个数，答案对 $10^9+7$ 取模。

第一行包含一个整数 $n$（$1 \leq n \leq 300$）——数组的长度。 第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$1 \leq a_{i} \leq 10^9$）——找到的数组。

输出一个整数，表示满足条件的正确排列的个数，对 $10^9+7$ 取模。

对于第一个示例： $[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$ 都不是完全平方数。 由 ChatGPT 5 翻译