#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vv = vector<vector<T>>;
template <class T>
inline bool MX(T &l, const T &r) {
  return l < r ? l = r, 1 : 0;
}
template <class T>
inline bool MN(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}
const ll MOD = 1e9 + 7;
ll modpow_(ll r, ll n, ll m = MOD) {
  ll re = 1, d = r % m;
  if (n < 0) (n %= m - 1) += m - 1;
  for (; n; n /= 2) {
    if (n & 1) (re *= d) %= m;
    (d *= d) %= m;
  }
  return re;
}
template <int mod = MOD>
struct ModInt {
  int v;
  ModInt(int v = 0) : v(v) {}
  ModInt operator+(const ModInt &n) const {
    return v + n.v < mod ? v + n.v : v + n.v - mod;
  }
  ModInt operator-(const ModInt &n) const {
    return v - n.v < 0 ? v - n.v + mod : v - n.v;
  }
  ModInt operator*(const ModInt &n) const { return ll(v) * n.v % mod; }
  ModInt operator/(const ModInt &n) const {
    return ll(v) * modpow_(n.v % mod, -1, mod) % mod;
  }
  ModInt operator+(const ll &n) const {
    return v + n < mod ? v + n : v + n - mod;
  }
  ModInt operator-(const ll &n) const {
    return v - n < 0 ? v - n + mod : v - n;
  }
  ModInt operator*(const ll &n) const { return ll(v) * (n % mod) % mod; }
  ModInt operator/(const ll &n) const {
    return ll(v) * modpow_(n % mod, -1, mod) % mod;
  }
  ModInt &operator+=(const ModInt &n) {
    v += n.v;
    if (v >= mod) v -= mod;
    return *this;
  }
  ModInt &operator-=(const ModInt &n) {
    v -= n.v;
    if (v < 0) v += mod;
    return *this;
  }
  ModInt &operator*=(const ModInt &n) {
    v = ll(v) * n.v % mod;
    return *this;
  }
  ModInt &operator/=(const ModInt &n) {
    v = ll(v) * modpow_(n.v, -1, mod) % mod;
    return *this;
  }
  ModInt &operator+=(const ll &n) {
    v += n;
    if (v >= mod) v -= mod;
    return *this;
  }
  ModInt &operator-=(const ll &n) {
    v -= n;
    if (v < 0) v += mod;
    return *this;
  }
  ModInt &operator*=(const ll &n) {
    v = ll(v) * n % mod;
    return *this;
  }
  ModInt &operator/=(const ll &n) {
    v = ll(v) * modpow_(n, -1, mod) % mod;
    return *this;
  }
  bool operator==(const ModInt &n) const { return v == n.v; };
  bool operator!=(const ModInt &n) const { return v != n.v; };
  ModInt &operator++() { return operator+=(1); }
  ModInt &operator--() { return operator-=(1); }
  ModInt operator++(int i) {
    ModInt tmp(*this);
    operator++();
    return tmp;
  }
  ModInt operator--(int i) {
    ModInt tmp(*this);
    operator--();
    return tmp;
  }
};
template <int mod>
ostream &operator<<(ostream &os, const ModInt<mod> &n) {
  return os << n.v;
};
template <int mod>
ModInt<mod> operator+(const ll &n, const ModInt<mod> &m) {
  return m.v + n < mod ? m.v + n : m.v + n - mod;
}
template <int mod>
ModInt<mod> operator-(const ll &n, const ModInt<mod> &m) {
  return n - m.v < 0 ? n - m.v + mod : n - m.v;
}
template <int mod>
ModInt<mod> operator*(const ll &n, const ModInt<mod> &m) {
  return ll(m.v) * (n % mod) % mod;
}
template <int mod>
ModInt<mod> operator/(const ll &n, const ModInt<mod> &m) {
  return ModInt<mod>(n % mod) / m;
}
template <int mod>
ModInt<mod> modpow(ModInt<mod> r, ll n) {
  ModInt<mod> re(1);
  if (n < 0) (n %= mod - 1) += mod - 1;
  for (; n; n /= 2) {
    if (n & 1) re *= r;
    r *= r;
  }
  return re;
}
vector<ModInt<MOD>> fact, finv, inv;
ModInt<MOD> comb(ll n, ll r) {
  if (n < r || r < 0) return 0;
  return fact[n] * finv[n - r] * finv[r];
}
class Doralion {
  void Modinvs(vector<ModInt<MOD>> &re, int n) {
    re.resize(n + 1);
    re[1] = 1;
    for (int i = 2; i <= n; ++i) re[i] = re[MOD % i] * (MOD - MOD / i);
  }
  void Facts(vector<ModInt<MOD>> &re, int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (int)(n); ++(i)) re[i + 1] = re[i] * (i + 1);
  }
  void Factinvs(vector<ModInt<MOD>> &re, const vector<ModInt<MOD>> &inv,
                int n) {
    re.resize(n + 1);
    re[0] = 1;
    for (int(i) = 0; (i) < (int)(n); ++(i)) re[i + 1] = re[i] * inv[i + 1];
  }

 public:
  Doralion(int n) {
    Modinvs(inv, n);
    Facts(fact, n);
    Factinvs(finv, inv, n);
  }
} doralion(1123456);
using pmm = pair<ModInt<MOD>, ModInt<MOD>>;
ModInt<MOD> modpow(ll r, ll n) { return modpow_(r, n); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  for (ll i = 2; i * i <= MOD; ++i) {
    ll d = i * i;
    for (auto &x : a)
      while (x % d == 0) x /= d;
  };
  map<int, int> cnt;
  for (auto x : a) ++cnt[x];
  vector<int> vs;
  for (auto [a, b] : cnt) vs.push_back(b);
  ;
  vector<ModInt<MOD>> dp(2 * n + 1);
  dp[0] = 1;
  for (auto v : vs) {
    vector<ModInt<MOD>> nxt(2 * n + 1);
    for (int(i) = 0; (i) < (int)(n + 1); ++(i)) {
      nxt[i + v] += dp[i];
      for (int(x) = (int)(1); (x) < (int)(v); ++(x)) {
        nxt[i + v - x] += dp[i] * comb(v, x) * fact[v - 1] * finv[v - x - 1];
      }
    }
    dp = nxt;
  };
  ModInt<MOD> re = 0;
  for (int(i) = 0; (i) < (int)(n + 1); ++(i)) {
    ModInt<MOD> tmp = dp[i] * fact[i];
    if (i % 2 == n % 2)
      re += tmp;
    else
      re -= tmp;
  }
  cout << re << "\n";
  return 0;
}
