#include <bits/stdc++.h>
using namespace std;
const int N = 333;
const int mod = 1e9 + 7;
int n, a[N], dp[2][N][N], cnt;
void get(int &x) {
  for (int i = (2), iE = (sqrt(x + 1)); i <= iE; i++)
    while (!(x % (i * i))) x /= (i * i);
}
int main() {
  scanf("%d", &n);
  for (int i = (1), iE = (n); i <= iE; i++) scanf("%d", &a[i]), get(a[i]);
  sort(a + 1, a + n + 1);
  dp[0][0][0] = 1;
  for (int i = (1), iE = (n); i <= iE; i++) {
    int t = (i & 1);
    if (a[i] != a[i - 1])
      for (int j = (0), jE = (i); j <= jE; j++)
        for (int k = (1), kE = (j); k <= kE; k++)
          (dp[t ^ 1][j][0] += dp[t ^ 1][j][k]) %= mod, dp[t ^ 1][j][k] = 0;
    if (a[i] != a[i - 1]) cnt = 0;
    memset(dp[t], 0, sizeof(dp[t]));
    for (int j = (0), jE = (i); j <= jE; j++)
      for (int k = (0), kE = (cnt); k <= kE; k++)
        (dp[t][j + 1][k + 1] += 1ll * (cnt * 2 - k) * dp[t ^ 1][j][k] % mod) %=
            mod;
    for (int j = (1), jE = (i); j <= jE; j++)
      for (int k = (0), kE = (cnt); k <= kE; k++)
        (dp[t][j - 1][k] += 1ll * (j - k) * dp[t ^ 1][j][k] % mod) %= mod;
    for (int j = (0), jE = (i); j <= jE; j++)
      for (int k = (0), kE = (cnt); k <= kE; k++)
        (dp[t][j][k] +=
         1ll * (i - cnt * 2 + 2 * k - j) * dp[t ^ 1][j][k] % mod) %= mod;
    cnt++;
  }
  printf("%d\n", dp[n & 1][0][0]);
  return 0;
}
