#include <bits/stdc++.h>
using namespace std;
int N;
signed long long mo = 1000000007;
signed long long ret = 1;
signed long long from[303][303];
signed long long to[303][303];
signed long long combi(int P_, int Q_) {
  static const int N_ = 1020;
  static signed long long C_[N_][N_];
  if (C_[0][0] == 0) {
    int i, j;
    for (i = 0; i < (N_); i++) C_[i][0] = C_[i][i] = 1;
    for (i = 1; i < N_; i++)
      for (j = 1; j < i; j++) C_[i][j] = (C_[i - 1][j - 1] + C_[i - 1][j]) % mo;
  }
  if (P_ < 0 || P_ > N_ || Q_ < 0 || Q_ > P_) return 0;
  return C_[P_][Q_];
}
signed long long hcomb(int P_, int Q_) {
  return (P_ == 0 && Q_ == 0) ? 1 : combi(P_ + Q_ - 1, Q_);
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  map<int, int> M;
  cin >> N;
  for (i = 0; i < (N); i++) {
    cin >> x;
    for (j = 2; j * j <= x; j++)
      while (x % (j * j) == 0) x /= j * j;
    M[x]++;
  }
  from[1][0] = 1;
  for (auto& r : M) {
    int cnt = r.second;
    for (j = 1; j <= cnt; j++) ret = ret * j % mo;
    memset(to, 0, sizeof(to));
    for (x = 0; x < (N + 2); x++)
      for (y = 0; y < (N + 2); y++)
        if (from[x][y]) {
          for (j = 1; j <= min(x + y, cnt); j++) {
            signed long long a = hcomb(j, cnt - j);
            int add = cnt - j;
            for (int z = 0; z <= min(j, x); z++) {
              int w = j - z;
              if (w > y) continue;
              signed long long b = combi(x, z);
              signed long long c = combi(y, w);
              (to[x + z + 2 * w][y - w + add] +=
               a * b % mo * c % mo * from[x][y]) %= mo;
            }
          }
        }
    swap(from, to);
  }
  cout << ret * from[N + 1][0] % mo << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
