#include <bits/stdc++.h>
using namespace std;
bool checksquare(long long a, long long b) {
  long long c = sqrt((long long)a * b);
  return (c * c == ((long long)a * b));
}
int main() {
  int n;
  cin >> n;
  vector<pair<int, int> > groups;
  long long num, gp_no;
  bool flag;
  for (long long i = 0; i < (long long)n; i++) {
    cin >> num;
    flag = false;
    for (long long j = 0; j < (long long)groups.size(); j++) {
      if (checksquare((long long)groups[j].first, num)) {
        flag = true;
        gp_no = j;
        break;
      }
    }
    if (!flag)
      groups.push_back(pair<int, int>(num, 1));
    else
      groups[gp_no].second += 1;
  }
  long long comb[301][301];
  long long fac[301];
  fac[0] = 1;
  for (long long i = 1; i < (long long)301; i++)
    fac[i] = (i * fac[i - 1]) % 1000000007;
  for (long long r = 0; r < (long long)301; r++) comb[0][r] = 0;
  for (long long n = 0; n < (long long)301; n++) comb[n][0] = 1;
  for (long long n = 1; n < (long long)301; n++) {
    for (long long r = 1; r < (long long)n + 1; r++) {
      comb[n][r] = (comb[n - 1][r - 1] + comb[n - 1][r]) % 1000000007;
    }
  }
  long long dp[302][302];
  dp[0][0] = 1;
  long long i, m, s = 1;
  for (int x = 0; x < groups.size(); x++) {
    m = groups[x].second;
    for (long long y = 0; y <= s; y++) {
      if (dp[x][y] == 0) continue;
      for (long long ij = 1; ij <= min(s, m); ij++) {
        for (long long j = 0; j <= min(y, ij); j++) {
          i = ij - j;
          long long &z = dp[x + 1][y - j + m - ij];
          long long d = dp[x][y];
          d = (d * comb[m - 1][ij - 1]) % 1000000007;
          d = (d * comb[y][j]) % 1000000007;
          d = (d * comb[s - y][i]) % 1000000007;
          z = (d + z) % 1000000007;
        }
      }
    }
    s += groups[x].second;
  }
  for (long long i = 0; i < (long long)groups.size(); i++)
    dp[groups.size()][0] =
        (dp[groups.size()][0] * fac[groups[i].second]) % 1000000007;
  cout << dp[groups.size()][0] << endl;
  return 0;
}
