#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int N, a[400], b[400], sum[400];
int C[400][400], Fac[400], dp[400][400];
inline bool is_sqr(long long x) {
  if (x < 9) return x == 1 || x == 4;
  long long L = 2, R = mod;
  while (L + 1 < R) {
    register long long mid = (L + R) >> 1, test = mid * mid - x;
    if (!test) return true;
    test < 0 ? L = mid : R = mid;
  }
  return false;
}
int main() {
  for (int i = 0; i <= 300; i++) C[i][0] = 1;
  for (int i = 1; i <= 300; i++)
    for (int j = 1; j <= 300; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  Fac[0] = 1;
  for (int i = 1; i <= 300; i++) Fac[i] = 1ll * Fac[i - 1] * i % mod;
  scanf("%d", &N);
  for (int i = 1; i <= N; i++) scanf("%d", a + i);
  int tot = 0;
  for (int i = 1; i <= N; i++)
    if (a[i]) {
      int cnt = 1;
      for (int j = i + 1; j <= N; j++)
        if (a[j] && is_sqr(1ll * a[i] * a[j])) cnt++, a[j] = 0;
      b[++tot] = cnt;
    }
  N = tot;
  for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + b[i];
  dp[1][b[1] - 1] = 1;
  for (int i = 1; i < N; i++)
    for (int j = 0; j < sum[i]; j++)
      if (dp[i][j]) {
        for (int x = 0; x <= sum[i] + 1 - j; x++)
          for (int y = 0; y <= j; y++)
            if (x + y > 0 && x + y <= b[i + 1])
              (dp[i + 1][b[i + 1] + j - x - (y << 1)] +=
               ((1ll * dp[i][j] * C[j][y] % mod) * C[sum[i] + 1 - j][x] % mod) *
               C[b[i + 1] - 1][x + y - 1] % mod) %= mod;
      }
  int ans = dp[N][0];
  for (int i = 1; i <= N; i++) ans = 1ll * ans * Fac[b[i]] % mod;
  printf("%d\n", ans);
  return 0;
}
