#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[302][302];
  long long fac[302];
  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;
  int s = 0;
  for (int i = 0; i < groups.size(); i++) {
    for (int j = 0; j <= s; j++) {
      if (dp[i][j] == 0) {
        continue;
      }
      for (int k = 1; k <= min(groups[i].second, s + 1); k++) {
        for (int l = 0; l <= min(j, k); l++) {
          long long &t = dp[i + 1][j - l + groups[i].second - k];
          long long d = dp[i][j];
          d = (d * comb[groups[i].second - 1][k - 1]) % 1000000007;
          d = (d * comb[j][l]) % 1000000007;
          d = (d * comb[s - j + 1][k - l]) % 1000000007;
          t = (t + d) % 1000000007;
        }
      }
    }
    s += groups[i].second;
  }
  int z = dp[groups.size()][0];
  for (int j = 0; j < groups.size(); j++) {
    z = (long long)z * fac[groups[j].second] % 1000000007;
  }
  printf("%d\n", z);
  return 0;
}
