一年前,Leha 在公园的长凳上发现了一个由 n 个数字组成的数组。 Leha 认为,如果对于所有 1 ≤ i < n 条件, api·api + 1 不是完全平方,则排列 p 是正确的。 Leha 想要找到模 109 + 7 的右排列数。
输入
输入数据的第一行包含单个整数 n (1 ≤ n ≤ 300) — 数组的长度。
下一行包含 n 个整数 a1, a2, ... , an (1 ≤ ai ≤ 109) — 找到的数组。
输出
输出单个整数 — 右排列模 109 + 7 的数量。
示例
输入 #1
3 1 2 4
输出 #1
2
输入 #2
7 5 2 4 2 4 1 1
输出 #2
144
注意
第一个例子:
[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 不是完全平方数。