#include <bits/stdc++.h>
using namespace std;
template <long long mod = 1000000007ll, bool slow_mul = false>
struct Binomial {
  bool is_table;
  vector<vector<long long> > binomial_table;
  int X, Y;
  void build_table() {
    binomial_table.assign(X, vector<long long>(Y, 0));
    for (int e = 0; e < X; e++) {
      for (int f = 0; f <= e; f++) {
        if (f == 0 || f == e)
          binomial_table[e][f] = 1;
        else {
          binomial_table[e][f] =
              binomial_table[e - 1][f - 1] + binomial_table[e - 1][f];
          if (binomial_table[e][f] >= mod) binomial_table[e][f] -= mod;
        }
      }
    }
  }
  Binomial(int SX, int SY) : X(SX + 2), Y(SY + 2) {
    is_table = true;
    build_table();
  }
  vector<long long> fact, ifact;
  int N;
  long long mul(long long a, long long b) {
    if (slow_mul) {
      long long ans = 0;
      for (; b; a = (a << 1) % mod, b >>= 1)
        if (b & 1) ans = (ans + a) % mod;
      return ans;
    } else {
      return a * b % mod;
    }
  }
  long long pw(long long a, long long b) {
    long long ans = 1;
    for (; b; a = mul(a, a), b >>= 1)
      if (b & 1) ans = mul(ans, a);
    return ans;
  }
  void build_fact() {
    fact.resize(N);
    ifact.resize(N);
    fact[0] = 1;
    for (int e = 1; e < N; e++) fact[e] = mul(fact[e - 1], e);
    ifact[N - 1] = pw(fact[N - 1], mod - 2);
    for (int e = N - 2; ~e; e--) ifact[e] = mul(ifact[e + 1], e + 1);
  }
  Binomial(int n) : N(n + 2) {
    is_table = false;
    build_fact();
  }
  long long get_coef(int n, int k) {
    if (k > n) return 0;
    if (k == n) return 1;
    if (is_table) {
      assert(n < X && k < Y);
      return binomial_table[n][k];
    } else {
      assert(n < N);
      long long res = fact[n];
      res = mul(res, ifact[k]);
      res = mul(res, ifact[n - k]);
      return res;
    }
  }
};
Binomial<> coef(100000);
const int mod = 1000000007;
const int maxn = 333;
vector<int> t;
long long a[maxn];
int v[maxn];
long long dp[2][maxn];
int main() {
  int n;
  cin >> n;
  for (int e = 0; e < n; e++) cin >> a[e];
  for (int e = 0; e < n; e++) {
    if (v[e]) continue;
    int cnt = 0;
    for (int f = e; f < n; f++) {
      if (v[f]) continue;
      long long pp = a[e] * a[f];
      long long t = sqrt(pp);
      if (a[e] * a[f] == t * t) {
        cnt++;
        v[f] = 1;
      }
    }
    t.push_back(cnt);
  }
  int tot = 0;
  dp[0][0] = 1;
  for (int v : t) {
    memset(dp[1], 0, sizeof(dp[1]));
    for (int f = 0; f < maxn; f++) {
      if (dp[0][f] == 0) continue;
      for (int S = 1; S <= min(v, tot + 1); S++)
        for (int D = 0; D <= min(f, S); D++) {
          long long mv = coef.fact[v];
          mv *= coef.get_coef(v - 1, S - 1);
          mv %= mod;
          mv *= coef.get_coef(f, D);
          mv %= mod;
          mv *= coef.get_coef(tot + 1 - f, S - D);
          mv %= mod;
          mv *= dp[0][f];
          mv %= mod;
          dp[1][f - D + v - S] += mv;
          if (dp[1][f - D + v - S] >= mod) dp[1][f - D + v - S] -= mod;
        }
    }
    memcpy(dp[0], dp[1], sizeof(dp[0]));
    tot += v;
  }
  cout << dp[0][0] << endl;
  return 0;
}
