#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
bool Max(T1 &a, T2 b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T1, typename T2>
bool Min(T1 &a, T2 b) {
  return a > b ? a = b, 1 : 0;
}
template <int MOD>
struct ModInt {
  unsigned x;
  ModInt() : x(0) {}
  ModInt(signed sig) : x(sig) {}
  ModInt(signed long long sig) : x(sig % MOD) {}
  int get() const { return (int)x; }
  ModInt pow(unsigned p) {
    ModInt res = 1, a = *this;
    while (p) {
      if (p & 1) res *= a;
      a *= a;
      p >>= 1;
    }
    return res;
  }
  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.power(MOD - 2); }
  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; }
};
const int N = 200001;
ModInt<1000000007> f[2][300];
ModInt<1000000007> C[301][301];
ModInt<1000000007> P[301];
bool isper(long long i) {
  long long t = sqrt(i);
  return t * t == i;
}
void solve() {
  int n;
  long long v;
  cin >> n;
  C[0][0] = 1;
  P[0] = 1;
  for (int i = 1; i <= (n); ++i) {
    C[i][0] = 1;
    P[i] = P[i - 1] * i;
    for (int j = 1; j <= (i); ++j) C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
  }
  vector<pair<long long, long long> > grp;
  for (int i = 0; i < (n); ++i) {
    cin >> v;
    bool found = 0;
    for (auto &e : grp) {
      if (isper(e.first * v)) {
        e.second++;
        found = 1;
        break;
      }
    }
    if (!found) grp.emplace_back(v, 1);
  }
  int c = 0;
  int sz = 0;
  f[0][0] = 1;
  for (auto &e : grp) {
    c ^= 1;
    int cur = e.second;
    for (int i = 0; i < (sz + cur); ++i) f[c][i] = 0;
    for (int sg = 1; sg <= (min(cur, sz + 1)); ++sg)
      for (int bad = 0; bad <= (max(0, sz - 1)); ++bad)
        for (int badsg = 0; badsg <= (min(bad, sg)); ++badsg) {
          f[c][cur - sg + bad - badsg] += f[!c][bad] * P[cur] *
                                          C[cur - 1][sg - 1] * C[bad][badsg] *
                                          C[sz + 1 - bad][sg - badsg];
        }
    sz += cur;
  }
  cout << f[c][0].x << '\n';
}
void init() {}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.setf(ios::fixed);
  cout.precision(20);
  init();
  int TC = 1;
  for (int TI = 1; TI <= (TC); ++TI) {
    solve();
  }
  return 0;
}
