← 返回题目列表

Codeforces · 840/C

C. 坐在替补席上

中文机器翻译题面 查看原题

一年前,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 不是完全平方数。