#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 10;
const int mod = 1e9 + 7;
int C[maxn][maxn], pro[maxn], inv[maxn], invpro[maxn];
int dp[maxn];
map<vector<int>, int> Map;
void Prepare() {
  for (int i = (0), _i = (maxn - 1); i <= _i; i++) C[i][0] = 1;
  for (int i = (1), _i = (maxn - 1); i <= _i; i++)
    for (int j = (1), _j = (i); j <= _j; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  inv[1] = 1;
  for (int i = (2), _i = (maxn - 1); i <= _i; i++)
    inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
  pro[0] = 1;
  invpro[0] = 1;
  for (int i = (1), _i = (maxn - 1); i <= _i; i++) {
    pro[i] = (long long)pro[i - 1] * i % mod;
    invpro[i] = (long long)invpro[i - 1] * inv[i] % mod;
  }
}
void divide(int x) {
  vector<int> p;
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) {
      int k = 0;
      while (x % i == 0) x /= i, k ^= 1;
      if (k) p.push_back(i);
    }
  if (x > 1) p.push_back(x);
  ++Map[p];
}
int solve(int n) {
  map<vector<int>, int>::iterator it;
  for (int i = (1), _i = (n); i <= _i; i++) dp[i] = 0;
  dp[0] = 1;
  for (it = Map.begin(); it != Map.end(); ++it) {
    int m = it->second;
    for (int i = n; i >= 0; --i) {
      int tmp = 0;
      for (int j = 1; j <= m && j <= i; ++j) {
        int t = (long long)dp[i - j] * C[m - 1][j - 1] % mod * invpro[j] % mod *
                pro[m] % mod;
        tmp += t;
        if (tmp < 0) tmp += mod;
        if (tmp >= mod) tmp -= mod;
      }
      dp[i] = tmp;
    }
  }
  int ans = 0;
  for (int i = 0; i <= n; ++i)
    ans = (ans + ((n - i) & 1 ? mod - 1LL : 1LL) * dp[i] % mod * pro[i] % mod) %
          mod;
  return ans;
}
int main() {
  Prepare();
  int n;
  for (; scanf("%d", &n) != EOF;) {
    Map.clear();
    for (int i = (1), _i = (n); i <= _i; i++) {
      int x;
      scanf("%d", &x);
      divide(x);
    }
    int ans = solve(n);
    printf("%d\n", ans);
  }
  return 0;
}
