#include <bits/stdc++.h>
using namespace std;
const long long N = 305;
const long long MOD = 1e9 + 7;
long long n, a[N], f[N][N], gt[N], cnt[N], total[N], num = 0, trau[N];
bool vs[N];
bool check(long long a, long long b) {
  long long t = sqrt(a * b);
  return t * t == a * b;
}
long long Pow(long long a, long long b) {
  if (b == 0) return 1;
  long long t = Pow(a, b / 2);
  if (b % 2 == 0) return t * t % MOD;
  return t * t % MOD * a % MOD;
}
long long C(long long a, long long b) {
  if (a > b) return 0;
  return gt[b] * trau[a] % MOD * trau[b - a] % MOD;
}
void in() {
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  gt[0] = 1, trau[0] = 1;
  for (long long i = 1; i <= n; i++) {
    gt[i] = gt[i - 1] * i % MOD;
    trau[i] = Pow(gt[i], MOD - 2) % MOD;
  }
  for (long long i = 1; i <= n; i++) {
    if (vs[i]) continue;
    cnt[++num] = 1;
    for (long long j = i + 1; j <= n; j++) {
      if (check(a[i], a[j])) cnt[num]++, vs[j] = true;
    }
  }
  for (long long i = 1; i <= num; i++) total[i] = total[i - 1] + cnt[i];
}
void add(long long &a, long long b) { a = (a + b) % MOD; }
void process() {
  f[1][cnt[1] - 1] = gt[cnt[1]];
  for (long long i = 1; i <= num - 1; i++)
    for (long long j = 0; j <= n; j++) {
      for (long long K = 1; K <= min(total[i] + 1, cnt[i + 1]); K++)
        for (long long X = 0; X <= min(j, K); X++) {
          if (f[i][j]) {
            long long S = cnt[i + 1];
            long long val = f[i][j] * gt[S] % MOD * C(K - 1, S - 1) % MOD *
                            C(X, j) % MOD * C(K - X, total[i] + 1 - j) % MOD;
            add(f[i + 1][j + S - K - X], val);
          }
        }
    }
  cout << f[num][0] << '\n';
}
int main() {
  if (fopen("trash.inp", "r"))
    freopen("trash.inp", "r", stdin), freopen("trash.out", "w", stdout);
  ios ::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  in();
  process();
}
