#include <bits/stdc++.h>
using namespace std;
using vi = vector<long long>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<pair<long long, long long> >;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
const long long inf = 1001001001001001001;
const long long INF = 1001001001;
const long long mod = 1000000007;
const double eps = 1e-10;
template <class T>
bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
void out(T a) {
  cout << a << '\n';
}
template <class T>
void outp(T a) {
  cout << '(' << a.first << ',' << a.second << ')' << '\n';
}
template <class T>
void outvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++)
    cout << '(' << v[i].first << ',' << v[i].second << ')';
  cout << '\n';
}
template <class T>
void outvvp(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outvp(v[i]);
}
template <class T>
void outv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) {
    if (i) cout << ' ';
    cout << v[i];
  }
  cout << '\n';
}
template <class T>
void outvv(T v) {
  for (long long i = 0; i < (long long)(v.size()); i++) outv(v[i]);
}
template <class T>
bool isin(T x, T l, T r) {
  return (l) <= (x) && (x) <= (r);
}
template <class T>
void yesno(T b) {
  if (b)
    out("yes");
  else
    out("no");
}
template <class T>
void YesNo(T b) {
  if (b)
    out("Yes");
  else
    out("No");
}
template <class T>
void YESNO(T b) {
  if (b)
    out("YES");
  else
    out("NO");
}
template <class T>
void noyes(T b) {
  if (b)
    out("no");
  else
    out("yes");
}
template <class T>
void NoYes(T b) {
  if (b)
    out("No");
  else
    out("Yes");
}
template <class T>
void NOYES(T b) {
  if (b)
    out("NO");
  else
    out("YES");
}
void outs(long long a, long long b) {
  if (a >= inf - 100)
    out(b);
  else
    out(a);
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long modpow(long long a, long long b) {
  long long res = 1;
  a %= mod;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
vi fac, finv, inv;
void init(long long n) {
  n *= 3;
  fac = vi(n + 5);
  finv = vi(n + 5);
  inv = vi(n + 5);
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (long long i = 2; i < (long long)(n + 5); i++) {
    fac[i] = fac[i - 1] * i % mod;
    inv[i] = mod - inv[mod % i] * (mod / i) % mod;
    finv[i] = finv[i - 1] * inv[i] % mod;
  }
}
long long modcom(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
int main() {
  long long n;
  cin >> n;
  init(2000);
  vi v(n);
  for (long long i = 0; i < (long long)(n); i++) cin >> v[i];
  for (long long i = 0; i < (long long)(n); i++) {
    for (long long j = 2; j < (long long)(inf); j++) {
      if (j * j > v[i]) break;
      while (v[i] % (j * j) == 0) v[i] /= j * j;
    }
  }
  sort(v.begin(), v.end());
  vi cnt;
  int l = -1;
  for (long long i = 0; i < (long long)(n); i++)
    if (i == n - 1 || v[i] != v[i + 1]) {
      cnt.emplace_back(i - l);
      l = i;
    }
  long long m = cnt.size();
  vi dp(n + 1);
  dp[cnt[0] - 1] = fac[cnt[0]];
  long long s = cnt[0];
  for (long long i = 1; i < (long long)(m); i++) {
    vi ndp(n + 1);
    for (long long j = 0; j < (long long)(n + 1); j++)
      if (dp[j]) {
        for (long long k = 0; k < (long long)(min(j, cnt[i]) + 1); k++)
          for (long long l = 0; l < (long long)(cnt[i] - k + 1); l++) {
            ndp[j - k + cnt[i] - k - l] += dp[j] * fac[cnt[i]] % mod *
                                           modcom(j, k) % mod *
                                           modcom(s + 1 - j, l) % mod *
                                           modcom(cnt[i] - 1, k + l - 1) % mod;
          }
      }
    for (long long i = 0; i < (long long)(n + 1); i++) dp[i] = ndp[i] % mod;
    s += cnt[i];
  }
  out(dp[0]);
}
