#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long n;
long long a[310], c[310], csum[310], dp[310][310], comb[505][505], na[310],
    fact[310], ifact[310], ways[310], old[310];
long long isPrime[100005];
vector<long long> primes;
pair<long long, long long> all[310];
long long modular_inverse(long long n, long long mod) {
  return pwr(n, mod - 2);
}
void cal() {
  for (long long i = 2; i < 100005; i++) isPrime[i] = 1;
  for (long long i = 2; i < 100005; i++) {
    if (isPrime[i]) {
      for (long long j = 2 * i; j < 100005; j += i) isPrime[j] = 0;
      primes.push_back(i);
    }
  }
  comb[0][0] = 1;
  for (long long i = 1; i < 505; i++) {
    comb[i][0] = 1;
    for (long long j = 1; j <= i; j++)
      comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % (1000000007LL);
  }
  fact[0] = 1;
  for (long long i = 1; i < 305; i++)
    fact[i] = (fact[i - 1] * i) % (1000000007LL);
  ifact[0] = 1;
  for (long long i = 1; i < 305; i++)
    ifact[i] =
        (ifact[i - 1] * modular_inverse(i, (1000000007LL))) % (1000000007LL);
}
int main() {
  scanf("%lld", &n);
  for (long long i = 0; i < n; i++) scanf("%lld", &a[i]);
  cal();
  for (long long i = 0; i < n; i++) {
    na[i] = 1;
    old[i] = a[i];
    for (long long j = 0; j < primes.size(); j++) {
      long long cnt = 0;
      while (a[i] % primes[j] == 0) {
        a[i] = a[i] / primes[j];
        cnt++;
      }
      if (cnt % 2 != 0) na[i] = na[i] * primes[j];
    }
    na[i] = na[i] * a[i];
  }
  for (long long i = 0; i < n; i++) {
    all[i].first = na[i];
    all[i].second = old[i];
  }
  sort(all, all + n);
  long long gp = 1;
  long long cnt = 1;
  long long prev = -1;
  for (long long i = 1; i < n; i++) {
    if (all[i].first != all[i - 1].first) {
      ways[gp] = fact[i - prev - 1];
      c[gp] = i - prev - 1;
      gp++;
      prev = i - 1;
    }
  }
  ways[gp] = fact[n - prev - 1];
  c[gp] = n - prev - 1;
  gp++;
  prev = n;
  csum[0] = c[0];
  for (long long i = 1; i < gp; i++) csum[i] = csum[i - 1] + c[i];
  dp[0][0] = 1;
  ways[0] = 1;
  for (long long i = 1; i < gp; i++) {
    for (long long usedgaps = 1; usedgaps <= min(csum[i - 1] + 1, c[i]);
         usedgaps++) {
      for (long long prevbadgaps = 0; prevbadgaps <= csum[i - 1] + 1;
           prevbadgaps++) {
        if (dp[i - 1][prevbadgaps] > 0) {
          for (long long badgaps = 0; badgaps <= min(usedgaps, prevbadgaps);
               badgaps++) {
            long long goodgaps = usedgaps - badgaps;
            long long prevgoodgaps = csum[i - 1] + 1 - prevbadgaps;
            dp[i][c[i] - usedgaps + prevbadgaps - badgaps] =
                (dp[i][c[i] - usedgaps + prevbadgaps - badgaps] +
                 ((((dp[i - 1][prevbadgaps] * comb[prevbadgaps][badgaps]) %
                    (1000000007LL) * comb[prevgoodgaps][goodgaps]) %
                   (1000000007LL) * comb[c[i] - 1][usedgaps - 1]) %
                  (1000000007LL)) *
                     ways[i]) %
                (1000000007LL);
          }
        }
      }
    }
  }
  printf("%lld\n", dp[gp - 1][0]);
  return 0;
}
