#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
void maximize(T &x, U y) {
  if (x < y) x = y;
}
template <class T, class U>
void minimize(T &x, U y) {
  if (x > y) x = y;
}
template <class T>
T Abs(T x) {
  return (x < 0 ? -x : x);
}
template <class T>
T safe_sqrt(T x) {
  return sqrt(max(x, (T)0));
}
template <class T, class U, class V>
T addmod(T x, U k, V MOD) {
  return ((x + k) % MOD + MOD) % MOD;
}
template <class T, class U, class V>
T submod(T x, U k, V MOD) {
  return ((x - k) % MOD + MOD) % MOD;
}
template <class T, class U, class V>
T mul(T x, U y, V MOD) {
  return (long long)x * y % MOD;
}
namespace task {
const int base = 1e9 + 7;
const int maxN = 3e2;
map<int, int> group;
int c[maxN + 2][maxN + 2], dp[maxN + 2][maxN + 2], f[maxN + 2], num[maxN + 2];
int n, m = 0;
void solve() {
  scanf("%d", &n);
  for (int x, i = 1; i <= n; ++i) {
    scanf("%d", &x);
    for (int j = 2; j * j <= x; ++j) {
      if (x % (j * j)) continue;
      while (!(x % (j * j))) x /= (j * j);
    }
    ++group[x];
  }
  for (__typeof((group).begin()) it = (group).begin(); it != (group).end();
       it++)
    num[++m] = it->second;
  for (int i = 0; i <= maxN; ++i)
    for (int j = 0; j <= i; ++j)
      c[i][j] = (i == j or !j ? 1 : addmod(c[i - 1][j - 1], c[i - 1][j], base));
  f[0] = 1;
  for (int i = 1; i <= maxN; ++i) f[i] = mul(f[i - 1], i, base);
  int all = 1;
  dp[0][0] = 1;
  for (int x = 1; x <= m; ++x, all += num[x - 1])
    for (int ij = 0; ij <= num[x]; ++ij)
      for (int y = 0; y <= all; ++y)
        if (dp[x - 1][y])
          for (int j = 0; j <= min(ij, y); ++j) {
            int i = ij - j;
            int z = all - y;
            int cnt = dp[x - 1][y];
            cnt = mul(cnt, c[z][i], base);
            cnt = mul(cnt, c[y][j], base);
            cnt = mul(cnt, c[num[x] - 1][ij - 1], base);
            cnt = mul(cnt, f[num[x]], base);
            dp[x][y - j + num[x] - ij] =
                addmod(dp[x][y - j + num[x] - ij], cnt, base);
          }
  printf("%d", dp[m][0]);
}
}  // namespace task
int main(void) { task::solve(); }
