#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}
template <int MOD>
struct ModInt {
  static const int Mod = MOD;
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
  ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
  int get() const { return (int)x; }
  ModInt &operator+=(ModInt that) {
    if ((x += that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    if ((x += MOD - that.x) >= MOD) x -= MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (unsigned long long)x * that.x % MOD;
    return *this;
  }
  ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
  ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
  ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
  ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
  ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b;
      std::swap(a, b);
      u -= t * v;
      std::swap(u, v);
    }
    return ModInt(u);
  }
  bool operator==(ModInt that) const { return x == that.x; }
  bool operator!=(ModInt that) const { return x != that.x; }
  ModInt operator-() const {
    ModInt t;
    t.x = x == 0 ? 0 : Mod - x;
    return t;
  }
};
template <int MOD>
ostream &operator<<(ostream &st, const ModInt<MOD> a) {
  st << a.get();
  return st;
};
template <int MOD>
ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
  ModInt<MOD> r = 1;
  while (k) {
    if (k & 1) r *= a;
    a *= a;
    k >>= 1;
  }
  return r;
}
template <typename T, int FAC_MAX>
struct Comb {
  vector<T> fac, ifac;
  Comb() {
    fac.resize(FAC_MAX, 1);
    ifac.resize(FAC_MAX, 1);
    for (int i = 1; i < FAC_MAX; i++) fac[i] = fac[i - 1] * i;
    for (int i = 1; i < FAC_MAX; i++) ifac[i] = T(1) / fac[i];
  }
  T aPb(int a, int b) {
    if (b < 0 || a < b) return T(0);
    return fac[a] * ifac[a - b];
  }
  T aCb(int a, int b) {
    if (b < 0 || a < b) return T(0);
    return fac[a] * ifac[a - b] * ifac[b];
  }
  T nHk(int n, int k) {
    if (n == 0 && k == 0) return T(1);
    if (n <= 0 || k < 0) return 0;
    return aCb(n + k - 1, k);
  }
};
int A[303], AA[303];
ModInt<1000000007> dp[303][403];
Comb<ModInt<1000000007>, 1010> com;
int N, B[303];
void _main() {
  cin >> N;
  for (int i = 0; i < N; i++) cin >> B[i];
  vector<long long> sqr;
  for (int i = 2; i < 101010; i++) sqr.push_back(1LL * i * i);
  sort(sqr.begin(), sqr.end(), greater<long long>());
  for (int i = 0; i < N; i++)
    for (auto &x : sqr)
      if (B[i] % x == 0) B[i] /= x;
  map<int, int> cnt;
  for (int i = 0; i < N; i++) cnt[B[i]]++;
  N = 0;
  for (auto &p : cnt)
    if (p.second) {
      A[N] = p.second;
      N++;
    }
  AA[0] = A[0];
  for (int i = 1; i < N; i++) AA[i] = AA[i - 1] + A[i];
  dp[0][0] = 1;
  for (int i = 0; i < N; i++)
    for (int c = 0; c < 303; c++) {
      int caninsert = 1;
      if (i) caninsert += AA[i - 1];
      if (A[i] == 0) {
        dp[i + 1][c] += dp[i][c];
        continue;
      }
      for (int g = 1; g < A[i] + 1; g++) {
        ModInt<1000000007> comb = com.aCb(A[i] - 1, g - 1);
        for (int dc = 0; dc < min(c, g) + 1; dc++) {
          if (dc <= c)
            if (0 <= caninsert - c)
              if (caninsert - c >= g - dc)
                if (0 <= g - dc) {
                  int ii = i + 1;
                  int cc = c - dc + A[i] - g;
                  dp[ii][cc] += dp[i][c] * comb * com.aCb(c, dc) *
                                com.aCb(caninsert - c, g - dc);
                }
        }
      }
    }
  ModInt<1000000007> ans = dp[N][0];
  for (int i = 0; i < N; i++) ans *= com.aPb(A[i], A[i]);
  cout << ans << endl;
}
