#include <bits/stdc++.h>
using namespace std;
const double PI = acos(0) * 2;
const double EPS = 1e-8;
const long long MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 1e9;
const double foo = 1e30;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcounll(s);
}
template <class T>
T sqr(T x) {
  return x * x;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
int vs[310];
long long fact[100100], inv[100100];
long long a[MAXN];
long long dp[310][310];
int n;
int has[MAXN];
long long power_mod(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b % 2) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
int check(long long u) {
  long long tmp = (long long)sqrt(u);
  if (tmp * tmp == u)
    return 1;
  else
    return 0;
}
long long C(int k, int n) {
  assert(k <= n);
  return fact[n] * inv[n - k] % MOD * inv[k] % MOD;
}
int main() {
  fact[0] = 1, inv[0] = 1;
  for (int i = 1; i < MAXN; i++)
    fact[i] = fact[i - 1] * i % MOD, inv[i] = power_mod(fact[i], MOD - 2);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  int tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i - 1; i >= 0; j--) {
      if (check(a[i] * a[j])) {
        vs[i] = vs[j];
        break;
      }
    }
    if (!vs[i]) vs[i] = ++tot;
    has[vs[i]]++;
  }
  dp[1][has[1] - 1] = fact[has[1]];
  int now = has[1];
  for (int i = 2; i <= tot; i++) {
    for (int j = 0; j < n; j++) {
      if (dp[i - 1][j]) {
        for (int k = 0; k <= min(now + 1, has[i]); k++) {
          for (int t = 0; t <= min(j, k); t++) {
            int nxt = j - t + has[i] - k;
            if (nxt < 0) continue;
            if (k - t > now + 1 - j) continue;
            (dp[i][nxt] += dp[i - 1][j] * C(k - 1, has[i] - 1) % MOD * C(t, j) %
                           MOD * C(k - t, now + 1 - j) % MOD) %= MOD;
          }
        }
      }
    }
    for (int j = 0; j < n; j++) dp[i][j] = dp[i][j] * fact[has[i]] % MOD;
    now += has[i];
  }
  cout << dp[tot][0];
}
