#include <bits/stdc++.h>
using namespace std;
long long n, a[310];
long long fac[310], rev[310];
bool mmp[310][310];
long long mod = (long long)1e9 + 7;
long long qmod(long long a, long long p) {
  long long ret = 1;
  while (p) {
    if (p & 1) ret = (ret * a) % mod;
    a = (a * a) % mod;
    p /= 2;
  }
  return ret;
}
void Init() {
  fac[0] = 1;
  for (int i = 1; i < 310; ++i) fac[i] = fac[i - 1] * i;
  rev[0] = 1;
  for (int i = 1; i < 310; ++i) rev[i] = qmod(fac[i], mod - 2);
}
long long C(int n, int m) { return fac[n] * rev[m] % mod * rev[n - m] % mod; }
bool isSqure(long long q) {
  long long sq = (long long)sqrt(q);
  return sq * sq == q;
}
void input() {
  istream& in = cin;
  in >> n;
  for (int i = 1; i <= n; ++i) in >> a[i];
}
bool vis[310];
int dfs(int p) {
  if (vis[p]) return 0;
  vis[p] = 1;
  int ret = 1;
  for (int i = 1; i <= n; ++i) {
    if (mmp[p][i]) {
      ret += dfs(i);
    }
  }
  return ret;
}
int num[310];
long long dp[310][310][310];
bool END[310];
void add(long long& a, long long b) {
  a %= mod;
  b %= mod;
  a = (a + b) % mod;
}
int main() {
  input();
  Init();
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) {
      if (isSqure(a[i] * a[j])) {
        mmp[i][j] = mmp[j][i] = 1;
      }
    }
  vector<int> block;
  for (int i = 1; i <= n; ++i) {
    int ret = dfs(i);
    if (ret) block.push_back(ret);
  }
  sort(block.begin(), block.end());
  reverse(block.begin(), block.end());
  int sum = 0;
  for (int p : block) {
    for (int i = 1; i <= p; ++i) num[sum + i] = i;
    sum += p;
    END[sum] = 1;
  }
  dp[0][0][0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= n + 1; ++j)
      for (int k = 0; k <= n + 1; ++k) {
        long long& ref = dp[i - 1][j][k];
        if (dp[i - 1][j][k] == 0) continue;
        int allslot = i;
        int prewa = j - k;
        int nowwa = k;
        int nookwaslot = (num[i] - 1) * 2 - 2 * nowwa;
        int okslot = allslot - j - nookwaslot;
        if (!END[i]) {
          if (j > 0) add(dp[i][j - 1][k], dp[i - 1][j][k] * prewa);
          add(dp[i][j + 1][k + 1], dp[i - 1][j][k] * nowwa);
          add(dp[i][j][k], dp[i - 1][j][k] * okslot);
          add(dp[i][j + 1][k + 1], dp[i - 1][j][k] * nookwaslot);
        } else {
          if (j > 0) add(dp[i][j - 1][0], dp[i - 1][j][k] * prewa);
          add(dp[i][j + 1][0], dp[i - 1][j][k] * nowwa);
          add(dp[i][j][0], dp[i - 1][j][k] * okslot);
          add(dp[i][j + 1][0], dp[i - 1][j][k] * nookwaslot);
        }
      }
  cout << dp[n][0][0] << endl;
  return 0;
}
