#include <bits/stdc++.h>
using namespace std;
const int MAXN = 301;
const int MOD = 1e9 + 7;
int n, k, have[MAXN];
multiset<int> arr;
long long dp[MAXN][MAXN], com[2 * MAXN][2 * MAXN], fac[MAXN];
void inp() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    arr.insert(x);
  }
  return;
}
bool check(long long s) {
  long double sq = sqrt(s);
  return int(sq) == sq;
}
void build() {
  while (arr.size()) {
    have[++k] = 1;
    auto it = arr.begin();
    int local = *it;
    set<int> delet;
    delet.insert(local);
    while (++it != arr.end()) {
      if (check((long long)(*it) * local)) {
        delet.insert(*it);
        have[k]++;
      }
    }
    for (auto i : delet) {
      arr.erase(i);
    }
  }
  return;
}
void comb_fac() {
  for (int i = 0; i < 2 * MAXN; i++) {
    for (int j = 0; j <= i; j++) {
      if (j == 0 || j == i) {
        com[j][i] = 1;
      } else {
        com[j][i] = (com[j][i - 1] + com[j - 1][i - 1]) % MOD;
      }
    }
  }
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) {
    fac[i] = (fac[i - 1] * i) % MOD;
  }
  return;
}
void dp_upt() {
  int sig = 0;
  for (int ind = 1; ind < k; ind++) {
    sig += have[ind];
    for (int now = 0; now < sig; now++) {
      for (int i = max(0, now - have[ind + 1]); i <= now + have[ind + 1]; i++) {
        for (int j = 0; j <= min(now, have[ind + 1]); j++) {
          int remain = now - j;
          remain = i - remain;
          int me = have[ind + 1] - j;
          if (remain < 0) {
            continue;
          }
          if (remain > me) {
            continue;
          }
          me -= remain;
          dp[ind + 1][i] += (((dp[ind][now] * com[me][sig + 1 - now] % MOD) *
                              com[j][now] % MOD) *
                             com[j + me - 1][remain + j + me - 1]) %
                            MOD;
          dp[ind + 1][i] %= MOD;
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(0);
  inp();
  build();
  comb_fac();
  dp[1][have[1] - 1] = 1;
  dp_upt();
  for (int i = 1; i <= k; i++) {
    dp[k][0] *= fac[have[i]];
    dp[k][0] %= MOD;
  }
  cout << dp[k][0] << endl;
  return 0;
}
