题目描述

小可是一名符文石收藏家，她拥有 $n$ 枚符文石，每枚石头内部蕴含一个古老的魔力值 $a_i$ （ $1 \le a_i \le 10^9$ ）。

小可发现，如果将石头排成一行，当相邻两块石头的魔力值乘积为完全平方数时，会触发古老的禁忌，导致符文失效。

因此，她想计算有多少种排列方式，可以避免触发任何禁忌。

你需要帮她求出相邻魔力值乘积均不是完全平方数的排列总数，结果对 $10^9+7$ 取模。

输入格式

输入有两行：

第一行一个正整数 $n$ ，表示小可拥有的石头个数。
第二行有 $n$ 个整数，第 $i$ 个整数 $a[i]$ 表示编号为 $i$ 的石头的魔力值。

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

4
2 2 3 4

9
2 4 8 9 12 4 3 6 11

【样例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≤n≤300$ ， $1≤a[i]≤10^9$ 。

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