#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const int N = 5e2 + 10;
const long long mod = 1e9 + 7;
const long long mod2 = 998244353;
const long long inf = 8e18;
const int LOG = 22;
long long pw(long long a, long long b, long long M) {
  return (!b ? 1
             : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M
                      : pw(a * a % M, b / 2, M)));
}
int A[N];
map<int, int> mp;
vector<int> v;
long long dp[N][N], first[N], I[N], ps[N];
inline long long E(long long r, long long n) {
  if (0 > r || r > n) return 0ll;
  return ((first[n] * I[r] % mod) * I[n - r] % mod);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  first[0] = 1;
  I[0] = pw(first[0], mod - 2, mod);
  for (long long i = 1; i < N; i++) {
    first[i] = (first[i - 1] * i) % mod;
    I[i] = pw(first[i], mod - 2, mod);
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
    long long now = 1;
    for (long long j = 2; j * j <= A[i]; j++) {
      int cnt = 0;
      while ((A[i] % j) == 0) {
        A[i] /= j;
        cnt++;
      }
      if (cnt % 2) {
        now *= j;
      }
    }
    if (A[i] > 1) {
      now *= A[i];
    }
    mp[now]++;
  }
  v.push_back(0);
  for (auto it = mp.begin(); it != mp.end(); it++) {
    v.push_back(it->second);
  }
  dp[0][0] = 1;
  int n2 = (int)v.size() - 1;
  for (int i = 1; i <= n2; i++) {
    ps[i] = ps[i - 1] + v[i];
    for (int j = 0; j <= n; j++) {
      for (int t = 0; t <= j; t++) {
        for (int k = 1; k <= v[i]; k++) {
          long long j2 = j - t + v[i] - k;
          if (j2 > (N - 1) || j2 < 0) {
            continue;
          }
          long long cu = ((((((dp[i - 1][j] * E(v[i] - k, v[i] - 1)) % mod) *
                             first[v[i]]) %
                            mod) *
                           E(t, j) % mod) *
                          E(k - t, ps[i - 1] + 1 - j)) %
                         mod;
          dp[i][j2] = (dp[i][j2] + cu) % mod;
        }
      }
    }
  }
  cout << dp[n2][0] << "\n";
  return 0;
}
