#include <bits/stdc++.h>
using namespace std;
const int M = 344;
const int mod = 1e9 + 7;
const int N = 314;
struct Fac {
  int num, cnt;
  friend bool operator!=(Fac x, Fac y) {
    if (x.num != y.num || x.cnt != y.cnt) return true;
    return false;
  }
};
bool cmp(Fac x, Fac y) { return x.num < y.num; }
int n;
int scnt[M];
int s[M];
vector<Fac> fac[M];
int item[M], itemlen;
int dp[M][M];
int fact[M], C[M][M];
void deal(int id) {
  Fac facget;
  int i, j, tmp, now;
  now = s[id];
  for (i = 2; i * i <= now; i++)
    if (now % i == 0) {
      facget.num = i;
      facget.cnt = 0;
      while (now % i == 0) {
        now /= i;
        facget.cnt++;
      }
      facget.cnt &= 1;
      if (facget.cnt) fac[id].push_back(facget);
    }
  if (now != 1) {
    facget.num = now;
    facget.cnt = 1;
    fac[id].push_back(facget);
  }
  sort(fac[id].begin(), fac[id].end(), cmp);
}
void init() {
  int i, j, the, tmp, sz, k;
  for (i = 1; i <= n; i++) fac[i].clear();
  for (i = 1; i <= n; i++) deal(i);
  memset(scnt, 0, sizeof(scnt));
  for (i = 1; i <= n; i++) {
    the = i;
    for (j = 1; j < i; j++)
      if (scnt[j] != 0 && fac[i].size() == fac[j].size()) {
        bool flag = true;
        for (k = 0; k < fac[i].size(); k++)
          if (fac[i][k] != fac[j][k]) {
            flag = false;
            break;
          }
        if (flag) the = j;
      }
    scnt[the]++;
  }
  itemlen = 0;
  for (i = 1; i <= n; i++)
    if (scnt[i] != 0) item[++itemlen] = scnt[i];
}
void up(int &x, int y) { x = (0ll + x + y) % mod; }
void mul(int &x, int y) { x = (1ll * x * y) % mod; }
bool cmpless(int x, int y) { return x > y; }
void solve() {
  int i, j, p, q, tmp, end;
  fact[1] = 1;
  for (i = 2; i <= N; i++) fact[i] = 1ll * fact[i - 1] * i % mod;
  memset(C, 0, sizeof(C));
  for (i = 0; i <= N; i++) C[i][0] = C[i][i] = 1;
  for (i = 1; i <= N; i++)
    for (j = 1; j < i; j++)
      up(C[i][j], (0ll + C[i - 1][j - 1] + C[i - 1][j]) % mod);
  memset(dp, 0, sizeof(dp));
  dp[1][item[1] - 1] = 1;
  end = item[1] - 1;
  for (i = 1; i < itemlen; i++) {
    for (j = 0; j <= end; j++)
      for (p = 1; p <= item[i + 1]; p++)
        for (q = max(0, (p + j - (end + i + 1))); q <= min(p, j); q++) {
          tmp = dp[i][j];
          mul(tmp, C[item[i + 1] - 1][p - 1]);
          mul(tmp, C[j][q]);
          mul(tmp, C[end + i + 1 - j][p - q]);
          up(dp[i + 1][j + (item[i + 1] - p) - q], tmp);
        }
    end += item[i + 1] - 1;
  }
  int ans = dp[itemlen][0];
  for (i = 1; i <= itemlen; i++) mul(ans, fact[item[i]]);
  printf("%d\n", ans);
}
int main() {
  int i, j;
  scanf("%d", &n);
  for (i = 1; i <= n; i++) scanf("%d", &s[i]);
  init();
  solve();
  return 0;
}
