#include <bits/stdc++.h>
using namespace std;
const int N = 302;
int n, sum, a[N], parent[N];
map<int, int> first;
vector<int> cnt;
long long dp[N][3 * N], fact[3 * N], revFac[3 * N];
long long comb(int n, int k) {
  if (n < k) return 0;
  if (n == k or !k) return 1;
  return fact[n] * revFac[n - k] % 1000000007 * revFac[k] % 1000000007;
}
long long power(long long b, long long p) {
  if (p == 0) return 1;
  long long sq = power(b, p / 2);
  sq = sq * sq % 1000000007;
  if (p & 1) sq = sq * b % 1000000007;
  return sq;
}
void computeFact() {
  fact[0] = fact[1] = 1;
  revFac[0] = revFac[1] = 1;
  for (int i = (1); i <= (int)(3 * N - 1); ++i) {
    fact[i] = fact[i - 1] * i % 1000000007;
    revFac[i] = power(fact[i], 1000000007 - 2);
  }
}
int find(int a) { return a == parent[a] ? a : parent[a] = find(parent[a]); }
void merge(int a, int b) { parent[find(a)] = parent[find(b)]; }
bool perfectSquare(long long x) {
  long long l = 1, r = 1000000000 + 2;
  while (l < r) {
    long long mid = (l + r) / 2;
    if (mid * mid >= x)
      r = mid;
    else
      l = mid + 1;
  }
  return l * l == x;
}
int main() {
  scanf("%d", &n);
  for (int i = (1); i <= (int)(n); ++i) scanf("%d", &a[i]), parent[i] = i;
  for (int i = (1); i <= (int)(n); ++i)
    for (int j = (i + 1); j <= (int)(n); ++j)
      if (perfectSquare(1ll * a[i] * a[j])) merge(i, j);
  for (int i = (1); i <= (int)(n); ++i) ++first[find(i)];
  for (pair<int, int> p : first) cnt.push_back(p.second);
  n = ((int)(cnt).size());
  computeFact();
  dp[0][cnt[0] - 1] = 1;
  for (int i = (0); i <= (int)(n - 2); ++i) {
    sum += cnt[i];
    for (int j = (0); j <= (int)(sum - 1); ++j)
      if (dp[i][j]) {
        for (int k = (1); k <= (int)(min(sum + 1, cnt[i + 1])); ++k) {
          for (int l = (0); l <= (int)(min(k, j)); ++l) {
            long long ways = comb(sum + 1 - j, k - l) * comb(j, l) %
                             1000000007 * comb(cnt[i + 1] - k + k - 1, k - 1) %
                             1000000007;
            dp[i + 1][j - l + cnt[i + 1] - 1 - (k - 1)] =
                (dp[i + 1][j - l + cnt[i + 1] - 1 - (k - 1)] +
                 dp[i][j] * ways % 1000000007) %
                1000000007;
          }
        }
      }
  }
  for (int i = (0); i <= (int)(n - 1); ++i)
    dp[n - 1][0] = dp[n - 1][0] * fact[cnt[i]] % 1000000007;
  cout << dp[n - 1][0];
}
