#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 20;
const double eps = 1e-8;
const long long mod = 1e9 + 7;
long long a[310];
long long fac[310];
long long inv[310];
void init() {
  fac[0] = fac[1] = 1;
  inv[0] = inv[1] = 1;
  for (long long i = 2; i < 310; i++) {
    fac[i] = fac[i - 1] * i % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
  }
  for (int i = 1; i < 310; i++) (inv[i] *= inv[i - 1]) %= mod;
}
long long C(long long n, long long k) {
  long long ans = 0;
  if (k > n) return ans;
  ans = ((fac[n] * inv[k] % mod) * inv[n - k]) % mod;
  return ans;
}
map<vector<int>, int> q;
long long dp[310];
int main() {
  init();
  int n;
  while (~scanf("%d", &n)) {
    q.clear();
    for (int i = 0; i < n; i++) scanf("%lld", a + i);
    for (int i = 0; i < n; i++) {
      std::vector<int> v;
      for (int j = 2; j * j <= a[i]; j++) {
        int cnt = 0;
        if (a[i] % j == 0) {
          while (a[i] % j == 0) {
            a[i] /= j;
            cnt++;
          }
        }
        if (cnt % 2) v.push_back((j));
      }
      if (a[i] > 1) v.push_back((a[i]));
      q[v]++;
    }
    memset((dp), 0, sizeof(dp));
    dp[0] = 1;
    for (auto cnt : q) {
      for (int i = n; i >= 0; i--) {
        long long t = 0;
        for (int k = 1; k <= cnt.second && k <= i; k++)
          t = (t +
               dp[i - k] * fac[cnt.second] % mod * C(cnt.second - 1, k - 1) %
                   mod * inv[k] % mod +
               mod) %
              mod;
        dp[i] = t;
      }
      cout << endl;
    }
    long long ans = 0;
    for (int i = 0; i <= n; i++) {
      if ((n - i) % 2)
        ans = (ans - fac[i] * dp[i] % mod + mod) % mod;
      else
        ans = (ans + fac[i] * dp[i] % mod + mod) % mod;
    }
    printf("%lld\n", ans);
  }
  return 0;
}
