#include <bits/stdc++.h>
using namespace std;
int dp[2][1 << 10], *cur = dp[0], *pre = dp[1];
int C[1000][1000] = {0}, fac[1000] = {1};
const int MOD = 1e9 + 7;
int category(int x) {
  for (int i = 2; i <= 32000; ++i) {
    while (x % (i * i) == 0) x /= i * i;
  }
  return x;
}
int split(int n, int i) { return C[n - 1][n - i]; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cur[0] = 1;
  C[0][0] = 1;
  for (int i = 1; i < 1000; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD;
  for (int i = 1; i < 1000; ++i)
    for (int j = 0; j < 1000; ++j)
      C[i][j] = j == 0 ? 1 : (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  int n;
  cin >> n;
  vector<int> A(n);
  for (int i = 0; i < n; ++i) cin >> A[i], A[i] = category(A[i]);
  sort(A.begin(), A.end());
  for (int i = 0, j = i; i < n; i = j) {
    swap(cur, pre);
    while (j < n and A[i] == A[j]) ++j;
    fill(cur, cur + 1000, 0);
    int a = j - i;
    for (int k = 0; k <= i; ++k) {
      for (int pkg = a; pkg >= 1; --pkg) {
        for (int cut = 0; cut <= min(k, pkg); ++cut) {
          if (k - cut + a - pkg >= 0 and i - k + cut + 1 >= 0) {
            (cur[k - cut + a - pkg] += 1ll * fac[a] * split(a, pkg) % MOD *
                                       pre[k] % MOD * C[k][cut] % MOD *
                                       C[i - k + 1][pkg - cut] % MOD) %= MOD;
          }
        }
      }
    }
  }
  cout << cur[0] << '\n';
}
