小可可是一个有着特殊爱好的人。他特别喜欢收集各种各样的球球，至今已经收集了 n 个球球。
小可可又是一个有着特殊想法的人。他将他的所有球球从 1 到 n 编号，并每天都把球球排成一个全新的排列。
小可可又是一个有着特殊情怀的人。他将每个球球的特点用 a[i]来表示（注意这里不同的球 a[i]可能相同）。
小可可又是一个爱恨分明的人。他十分讨厌平方数，所以他规定：一个排列 p，对于所有的  `1 ≤ i < n，a[p_i]×a[p_{i+1}]` 不是一个平方数，这样的排列 p 才是合法的。
小可可一直坚持每天排一个全新的合法的排列。有一天，他心血来潮，想知道所有合法排列的个数。小可可十分强，他当然知道怎么算。不过，他想用这个题来考考身在考场的你。这个数可能太大了，所以你只需要告诉小可可合法排列个数对 `10^9 +7` 取模的结果就可以了。
你能正确回答小可可的问题吗？如果能的话，他说不定会送个球球给你呢……

第一行一个正整数 n，表示小可可拥有的球球个数。
第二行有 n 个整数，第 i 个整数 a[i]表示编号为 i 的球球的特点。

输出一行，包括一个正整数，表示合法排列个数对 `10^9 +7`（即 1000000007）取模的结果。

4
2 2 3 4

12

9
2 4 8 9 12 4 3 6 11

99360