#include <bits/stdc++.h>
using namespace std;
const long long mod = (int)(1e9) + 7;
long long A[510];
long long C[510][510];
long long dp[310][500];
int n;
int seq[310];
int belong[310], a[310];
void pre() {
  A[0] = A[1] = 1;
  for (int i = 2; i < 500; ++i) {
    A[i] = A[i - 1] * i % mod;
  }
  for (int i = 0; i < 500; ++i) {
    C[0][i] = 1;
    for (int j = 1; j <= i; ++j) {
      C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % mod;
    }
  }
}
int solve() {
  memset(dp, 0, sizeof(dp));
  dp[1][seq[1] - 1] = 1;
  long long sum = seq[1];
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < sum; ++j) {
      for (int k = 1; k <= seq[i]; ++k) {
        for (int h = 0; h <= j && h <= k; ++h) {
          dp[i][j - h + seq[i] - k] += dp[i - 1][j] * C[h][j] % mod *
                                       C[k - h][sum + 1 - j] % mod *
                                       C[k - 1][seq[i] - 1] % mod;
          dp[i][j - h + seq[i] - k] %= mod;
        }
      }
    }
    sum += seq[i];
  }
  long long ret = dp[n][0];
  for (int i = 1; i <= n; ++i) {
    ret = ret * A[seq[i]] % mod;
  }
  return ret;
}
bool ok(int i, int j) {
  long long p = (long long)a[i] * a[j];
  long long q = sqrt(p);
  if (q * q == p)
    return 1;
  else
    return 0;
}
void getseq() {
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
  }
  int nn = 0;
  for (int i = 1; i <= n; ++i) {
    if (belong[i] == 0) {
      int num = 1;
      belong[i] = ++nn;
      for (int j = i + 1; j <= n; ++j)
        if (ok(i, j)) {
          belong[j] = nn;
          num++;
        }
      seq[nn] = num;
    }
  }
  n = nn;
}
int main() {
  pre();
  scanf("%d", &n);
  getseq();
  printf("%d\n", solve());
  return 0;
}
