#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
const int N = 405;
const int MOD = 1000000007;
int T, lim, n, k, l, p, cnt, id[N];
long long C[N][N], a[N], dp[N][N], fac[N] = {1};
vector<int> G[N];
bool Judge(long long x) {
  long long k = sqrt(x);
  return k * k == x;
}
void init() {
  C[0][0] = 1LL;
  for (int i = 1; i <= 350; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    fac[i] = fac[i - 1] * i % MOD;
  }
  id[1] = cnt = 1, G[1].push_back(1);
  for (int i = 2; i <= n; i++) {
    bool flag = true;
    for (int j = i - 1; j >= 1; j--)
      if (Judge(a[j] * a[i])) {
        G[id[j]].push_back(i);
        id[i] = id[j];
        flag = false;
        break;
      }
    if (flag) {
      id[i] = ++cnt;
      G[cnt].push_back(i);
    }
  }
}
signed main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", a + i);
  init();
  dp[1][(int)G[1].size() - 1] = 1;
  lim = (int)G[1].size();
  for (int i = 2; i <= cnt; i++) {
    int sz = G[i].size();
    for (int k = 0; k < sz; k++)
      for (int j = 0; j < lim; j++)
        for (int p = 0; p <= min(j, k + 1); p++) {
          dp[i][j + sz - k - 1 - p] += dp[i - 1][j] * C[sz - 1][k] % MOD *
                                       C[j][p] % MOD *
                                       C[lim + 1 - j][k + 1 - p] % MOD;
          dp[i][j + sz - k - 1 - p] %= MOD;
        }
    lim += sz;
  }
  long long res = dp[cnt][0];
  for (int i = 1; i <= cnt; i++) res = res * fac[(int)G[i].size()] % MOD;
  printf("%lld\n", res);
  return 0;
}
