#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long maxn = 510;
long long fac[maxn];
long long dp[maxn][maxn];
long long c[maxn][maxn];
long long a[maxn], cnt[maxn];
bool vis[maxn];
long long n, sz;
bool perfect_square(long long x) {
  long long l = 1, r = 1e9;
  long long now = l;
  while (l <= r) {
    long long mid = (l + r) >> 1;
    if (mid * mid <= x) {
      now = mid;
      l = mid + 1;
    } else
      r = mid - 1;
  }
  return now * now == x;
}
void get_comb() {
  c[0][0] = 1;
  fac[0] = 1;
  for (long long i = 1; i <= 300; i++) {
    c[i][0] = 1;
    for (long long j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j] % mod + c[i - 1][j - 1] % mod) % mod;
    }
  }
  for (long long i = 1; i <= 300; i++) fac[i] = (fac[i - 1] * i) % mod;
}
void slove() {
  dp[0][cnt[0] - 1] = 1;
  long long lim = cnt[0];
  for (long long i = 1; i < sz; i++) {
    for (long long j = 0; j < lim; j++) {
      for (long long k = 0; k < cnt[i]; k++) {
        for (long long m = 0; m <= min(j, k + 1); m++) {
          long long ways = c[cnt[i] - 1][k] % mod * c[j][m] % mod *
                           c[lim - 1 - j + 2][k + 1 - m] % mod;
          dp[i][j + cnt[i] - 1 - k - m] =
              (dp[i][j + cnt[i] - 1 - k - m] + dp[i - 1][j] * ways % mod) % mod;
        }
      }
    }
    lim += cnt[i];
  }
  long long ans = dp[sz - 1][0];
  for (long long i = 0; i < sz; i++) {
    ans *= fac[cnt[i]];
    ans %= mod;
  }
  cout << ans << endl;
}
int main() {
  scanf("%I64d", &n);
  for (long long i = 0; i < n; i++) scanf("%I64d", &a[i]);
  for (long long i = 0; i < n; i++) {
    if (vis[i] == 0) {
      for (long long j = i; j < n; j++) {
        if (perfect_square(1LL * a[i] * a[j])) {
          cnt[sz]++;
          vis[j] = 1;
        }
      }
      sz++;
    }
  }
  get_comb();
  slove();
  return 0;
}
