#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long inv(long long a) {
  if (a == 1) return a;
  return inv(mod % a) * (mod - mod / a) % mod;
}
long long C[305][305];
long long F[305], invF[305];
long long dp[305][305];
void init() {
  C[0][0] = 1;
  C[1][0] = C[1][1] = 1;
  F[0] = F[1] = 1;
  invF[0] = invF[1] = 1;
  for (int i = int(2); i < int(301); ++i) {
    F[i] = (F[i - 1] * i) % mod;
    invF[i] = inv(F[i]);
    C[i][0] = C[i][i] = 1;
    for (int j = int(1); j < int(i); ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
}
map<int, int> mp;
int main() {
  init();
  int n;
  while (scanf("%d", &n) == 1) {
    mp.clear();
    for (int i = int(0); i < int(n); ++i) {
      int a;
      scanf("%d", &a);
      int p = 1;
      for (int d = 2; d * d <= a; d++) {
        if (a % d == 0) {
          int cnt = 0;
          while (a % d == 0) {
            a /= d;
            cnt++;
          }
          if (cnt & 1) p *= d;
        }
      }
      if (a > 1) p *= a;
      mp[p]++;
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int cnt = 1;
    for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) {
      int p = (*it).second;
      for (int i = int(0); i < int(n + 1); ++i) {
        for (int j = int(1); j < int(i + 1); ++j) {
          if (j > p) break;
          long long pans = 1;
          pans *= F[p];
          pans *= C[p - 1][j - 1];
          pans %= mod;
          pans *= invF[j];
          pans %= mod;
          dp[cnt][i] += (dp[cnt - 1][i - j] * pans);
          dp[cnt][i] %= mod;
        }
      }
      cnt++;
    }
    long long ans = 0;
    for (int i = int(n + 1 - 1); i >= int(0); --i) {
      long long pans = F[i] * dp[cnt - 1][i];
      pans %= mod;
      if ((n - i) & 1)
        ans -= pans;
      else
        ans += pans;
      ans = ((ans % mod) + mod) % mod;
    }
    printf("%lld\n", ans);
  }
}
