#include <bits/stdc++.h>
using namespace std;
const int MAX = 303;
const int MOD = 1e9 + 7;
long long ncr[MAX][MAX];
map<int, int> cnt;
int tot[MAX];
long long dp[MAX][MAX];
vector<int> fin;
int get(int a) {
  int ans = 1;
  for (int i = 2; (i * i) <= a; i++) {
    int k = 0;
    while ((a % i) == 0) {
      a /= i;
      k ^= 1;
    }
    if (k) {
      ans *= i;
    }
  }
  ans *= a;
  return ans;
}
int main() {
  for (int i = 0; i < MAX; i++) {
    ncr[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % MOD;
    }
  }
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int a;
    scanf("%d", &a);
    cnt[get(a)]++;
  }
  for (auto x : cnt) {
    fin.push_back(x.second);
  }
  sort(fin.begin(), fin.end());
  reverse(fin.begin(), fin.end());
  int m = fin.size();
  for (int i = 1; i <= m; i++) {
    tot[i] = tot[i - 1] + fin[i - 1];
  }
  dp[1][fin[0] - 1] = 1;
  for (int i = 2; i <= m; i++) {
    int slots = tot[i - 1] + 1;
    for (int j = 0; j <= n; j++) {
      if (!dp[i - 1][j]) {
        continue;
      }
      for (int k = 1; k <= min(slots, fin[i - 1]); k++) {
        for (int l = 0; l <= min(j, k); l++) {
          dp[i][fin[i - 1] - k + j - l] +=
              (((((dp[i - 1][j] * ncr[j][l]) % MOD) *
                 ncr[fin[i - 1] - 1][k - 1]) %
                MOD) *
               ncr[slots - j][k - l]) %
              MOD;
          dp[i][fin[i - 1] - k + j - l] %= MOD;
        }
      }
    }
  }
  long long ans = dp[m][0];
  for (int i = 0; i < m; i++) {
    for (int j = 1; j <= fin[i]; j++) {
      ans = (ans * j) % MOD;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
