#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int MAX = 100010;
const int md = 1e9 + 7;
int n, a[N];
int d[MAX];
int C[N][N];
map<int, int> cnt;
int f[N][N];
void sieve() {
  d[0] = d[1] = 1;
  for (int i = 2; i < MAX; ++i)
    if (!d[i]) {
      for (int j = i + i; j < MAX; j += i) d[j] = 1;
    }
}
void prep() {
  for (int i = 0; i < N; ++i) C[i][0] = 1;
  for (int i = 1; i < N; ++i) {
    for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % md;
  }
}
int nCk(int n, int k) {
  if (n < 0 || k < 0 || n < k)
    return 0;
  else
    return C[n][k];
}
void add(int &a, int b) {
  a += b;
  while (a >= md) a -= md;
  if (a < 0) a += md;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  prep();
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x;
    cin >> x;
    for (int j = 2; j * j <= x; ++j)
      if (!d[j] && x % (j * j) == 0) {
        while (x % (j * j) == 0) x /= (j * j);
      }
    cnt[x]++;
  }
  n = 0;
  for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); ++it) {
    a[++n] = it->second;
  }
  f[0][0] = 1;
  int sum = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= sum; ++j)
      if (f[i - 1][j]) {
        for (int k = 0; k <= sum && k <= a[i]; ++k)
          for (int z = 0; z <= k && z <= j; ++z) {
            int v = 1LL * nCk(sum - j, k - z) * nCk(j, z) % md;
            v = 1LL * v * nCk(a[i] - 1, k - 1) % md;
            add(f[i][j - z + a[i] - k], 1LL * v * f[i - 1][j] % md);
          }
      }
    sum += a[i];
  }
  int ans = f[n][0];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= a[i]; ++j) ans = 1LL * ans * j % md;
  }
  cout << ans << endl;
}
