4497. Ruyi的书架

【题目背景】

有一天，你来到了 $Ruyi$ 的家里面，发现他的书乱糟糟的。

为了让他的家里变得整洁，于是你们共同开始整理书架。

【题目描述】

$Ruyi$ 喜欢读一些书，你需要帮助他整理他的书架。

因为 $Ruyi$ 发现一段时间一直读一种类型的书非常的无聊，所以他不希望把类似的书放在一起。

具体来说，每本书有个内容值 $a_i$，如果两本相邻的书满足 $a_i * a_{i+1}$ 是个完全平方数，$Ruyi$ 就会因为太无聊而不读这些书。

有一天你心血来潮，想帮 $Ruyi$ 整理书架，由于 $Ruyi$ 希望能每天坚持读书，所以他想询问有多少种排列方案数，满足相邻的两本书都不无聊，由于这个数可能太大了，所以你只需要输出可能的方案数对 $10^9+7$ 取模的结果就可以了。

你能正确的回答 $Ruyi$ 这个问题吗，如果可以的话，$Ruyi$ 说不定会送你本书呢……

大样例

【输入格式】

输入有两行：

第一行一个正整数 $n$，表示 $Ruyi$ 拥有的书个数。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示编号为 $i$ 的球球的内容值。

【输出格式】

输出一个整数，表示可能的排列数对 $10^9+7$ 取模的结果

【样例输入1】

4
2 2 3 4

【样例输出】

12

【样例输入2】

9
2 4 8 9 12 4 3 6 11

【样例输出】

99360

【样例说明】

[样例 1 解释] :

$12$ 种合法的排列分别为：

$1,3,2,4$

$2,3,1,4$

$3,1,4,2$

$3,2,4,1$

$1,3,4,2$

$2,3,4,1$

$1,4,2,3$

$2,4,1,3$

$4,1,3,2$

$4,2,3,1$

$1,4,3,2$

$2,4,3,1$

【数据规模与约定】

对于 $100\%$ 的数据满足：$1\le n\le 300$，$1 \le a_i \le 10^9$。

本题共 $10$ 个测试点，编号为 $1 \sim 10$，每个测试点额外保证如下：

测试点编号 |$n$ 的范围    |$a_i$ 的范围

$1 \sim 2$          |$n\le 10$      |$a_i\le 10^9$

$3 \sim 4$          |$n\le 300$    |$a_i\le 2$

$5 \sim 7$          |$n\le 300$    |$a_i\le 10^9$ 且 $a_i$ 是质数

$8 \sim 10$        |$n\le 300$    |$a_i\le 10^9$