#include <bits/stdc++.h>
using namespace std;
int n;
long long a[300];
bool isMain[300];
int available[300];
int numClasses;
vector<int> classes;
long long dp[300 + 1][300];
long long C[300 + 1][300 + 1];
long long fact[300 + 1];
bool solvedC[300 + 1][300 + 1];
bool solvedF[300 + 1];
long long choose(int i, int j) {
  if (i < 0 || j < 0 || j > i) return 0;
  if (solvedC[i][j]) return C[i][j];
  if (solvedC[i][i - j]) {
    C[i][j] = C[i][i - j];
  } else if (i == 0) {
    C[i][j] = 1;
  } else {
    C[i][j] = (choose(i - 1, j) + choose(i - 1, j - 1)) % 1000000007;
  }
  solvedC[i][j] = true;
  return C[i][j];
}
long long factorial(int i) {
  if (solvedF[i]) return fact[i];
  if (i == 0)
    fact[i] = 1;
  else
    fact[i] = (i * factorial(i - 1)) % 1000000007;
  solvedF[i] = true;
  return fact[i];
}
bool isSquare(long long s) {
  long long sq = (long long)round(sqrt(s));
  return (sq) * (sq) == s;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < (n); i++) {
    cin >> a[i];
    isMain[i] = true;
    available[i] = 1;
    for (int j = 0; j < (i); j++) {
      if (isSquare(a[j] * a[i])) {
        isMain[i] = false;
        available[j]++;
        break;
      }
    }
  }
  for (int i = 0; i < (n); i++) {
    if (isMain[i]) {
      numClasses++;
      classes.push_back(available[i]);
    }
  }
  int numSoFar = classes[0];
  dp[0][classes[0] - 1] = factorial(classes[0]);
  for (int i = (1); i < (numClasses); i++) {
    int nextSoFar = numSoFar + classes[i];
    for (int j = 0; j < (nextSoFar); j++) {
      for (int k = 0; k < (numSoFar); k++) {
        for (int numKeep = 0; numKeep < (min(j + 1, k + 1)); numKeep++) {
          int numSpent = k - numKeep;
          int stillHave = classes[i] - numSpent;
          int numNew = j - numKeep;
          if (numNew > stillHave) continue;
          int canFill = numSoFar + 1 - k;
          dp[i][j] += ((((((dp[i - 1][k] * choose(k, numSpent)) % 1000000007) *
                          choose(canFill, stillHave - numNew)) %
                         1000000007) *
                        choose(classes[i] - 1, classes[i] - numNew - 1)) %
                       1000000007 * factorial(classes[i])) %
                      1000000007;
          dp[i][j] %= 1000000007;
        }
      }
    }
    numSoFar = nextSoFar;
  }
  cout << dp[numClasses - 1][0] << "\n";
  return 0;
}
