#include <bits/stdc++.h>
using namespace std;
int n, m, A[310];
vector<pair<int, int> > vec;
int sum[310];
long long f[310][310];
long long C[310][310], fac[310];
void prepare() {
  int i, j;
  for (i = 1, fac[0] = 1; i <= 300; i++) fac[i] = fac[i - 1] * i % 1000000007;
  for (i = 0; i <= 300; i++)
    for (j = 1, C[i][0] = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
}
void input() {
  int i, j;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
    for (j = 0; j < vec.size(); j++) {
      double t = sqrt(1LL * vec[j].first * A[i]);
      if (fabs(t - (long long)t) < 1e-9) {
        vec[j].second++;
        break;
      }
    }
    if (j >= vec.size()) vec.push_back(pair<int, int>(A[i], 1));
  }
  m = vec.size();
  for (i = 1, sum[0] = vec[0].second; i < m; i++)
    sum[i] = sum[i - 1] + vec[i].second;
}
void dp() {
  int i, j, k, l, x, y;
  f[0][vec[0].second - 1] = fac[vec[0].second];
  for (i = 1; i < m; i++) {
    x = vec[i].second;
    for (j = 0; j < sum[i - 1]; j++)
      for (k = 1; k <= x; k++)
        for (l = 0; l <= j && l <= k; l++) {
          if ((y = j - l + x - k) >= sum[i]) continue;
          f[i][y] =
              (f[i][y] + f[i - 1][j] * C[x - 1][k - 1] % 1000000007 * C[j][l] %
                             1000000007 * C[sum[i - 1] + 1 - j][k - l] %
                             1000000007 * fac[x]) %
              1000000007;
        }
  }
}
int main() {
  prepare();
  input();
  dp();
  printf("%I64d", f[m - 1][0]);
  return 0;
}
