#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 3e2 + 10;
const long long Mod = 1e9 + 7;
long long dp[MAXN][MAXN];
long long a[MAXN];
long long e[MAXN];
long long z[MAXN];
long long rev[MAXN];
long long fact[MAXN];
long long pw(long long x, long long n) {
  if (n == 0) {
    return 1;
  }
  long long w = pw(x, n / 2);
  w *= w;
  w %= Mod;
  if (n & 1) {
    w *= x;
    w %= Mod;
  }
  return w;
}
long long c(long long n, long long k) {
  if (k > n || k < 0 || n < 0) {
    return 0;
  }
  return fact[n] * ((rev[k] * rev[n - k]) % Mod) % Mod;
}
bool issq(long long x) {
  long long sq = sqrt(x);
  for (long long i = sq; i < sq + 4; i++) {
    if (i * i == x) {
      return true;
    }
  }
  for (long long i = sq; i > sq - 4; i--) {
    if (i * i == x) {
      return true;
    }
  }
  return false;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  long long n, t = 1, total = 0;
  cin >> n;
  fact[0] = 1;
  rev[0] = 1;
  for (long long i = 1; i < MAXN; i++) {
    fact[i] = fact[i - 1] * i;
    fact[i] %= Mod;
    rev[i] = pw(fact[i], Mod - 2);
  }
  for (long long i = 1; i <= n; i++) {
    cin >> a[i];
    bool flag = false;
    for (long long j = 1; j < i; j++) {
      if (issq(a[i] * a[j])) {
        e[z[j]]++;
        flag = true;
        break;
      }
    }
    if (!flag) {
      z[i] = t;
      e[t]++;
      t++;
    }
  }
  dp[0][0] = 1;
  for (long long i = 1; i < t; i++) {
    for (long long j = 0; j <= total + e[i]; j++) {
      for (long long u = 0; u <= total; u++) {
        for (long long w = 0; w <= min(e[i], u); w++) {
          long long s = dp[i - 1][u];
          s *= c(u, w);
          s %= Mod;
          s *= c(total - u + 1, u + e[i] - 2 * w - j);
          s %= Mod;
          s *= c(e[i] - 1, u + e[i] - w - j - 1);
          s %= Mod;
          s *= fact[e[i]];
          s %= Mod;
          dp[i][j] += s;
          dp[i][j] %= Mod;
        }
      }
    }
    total += e[i];
  }
  cout << dp[t - 1][0];
}
