#include <bits/stdc++.h>
using namespace std;
int n;
long long A[307] = {0};
int fa[307] = {0}, B[307] = {0}, C[307] = {0};
long long dp[307][307] = {0}, f[307] = {0}, g[307][307] = {0};
bool flagf[307] = {0}, flagg[307][307] = {0};
inline bool square(long long x) {
  long long y = (long long)sqrt((double)x);
  return y * y == x || (y + 1) * (y + 1) == x;
}
long long fac(int a) {
  if (!a) return 1;
  if (flagf[a]) return f[a];
  flagf[a] = true;
  return f[a] = (a * fac(a - 1)) % 1000000007LL;
}
long long com(int a, int b) {
  if (a < b) return 0;
  if (b == 0) return 1;
  if (flagg[a][b]) return g[a][b];
  flagg[a][b] = true;
  g[a][b] = (com(a - 1, b - 1) + com(a - 1, b)) % 1000000007LL;
  return g[a][b];
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
  for (int i = 1; i <= n; i++) {
    int q = 0;
    for (int j = 1; j < i; j++)
      if (square(A[i] * A[j])) {
        q = j;
        break;
      }
    if (q)
      B[fa[q]]++;
    else {
      fa[i] = ++B[0];
      B[B[0]] = 1;
    }
  }
  int m = B[0];
  B[0] = 0;
  for (int i = 1; i <= m; i++) C[i] = B[i] + C[i - 1];
  dp[0][0] = 1;
  for (int i = 1; i < 307; i++) dp[0][i] = 0;
  for (int i = 0; i < m; i++)
    for (int j = 0; j <= C[i] + 1; j++)
      if (dp[i][j]) {
        int xl = min(C[i] + 1, B[i + 1]);
        for (int x = 1; x <= xl; x++) {
          int yl = min(x, j);
          for (int y = 0; y <= yl; y++) {
            long long res;
            res = (com(j, y) * com(C[i] + 1 - j, x - y)) % 1000000007LL;
            res = (res * com(B[i + 1] - 1, x - 1)) % 1000000007LL;
            res = (res * dp[i][j]) % 1000000007LL;
            res = (res * fac(B[i + 1])) % 1000000007LL;
            dp[i + 1][j - y + B[i + 1] - x] += res;
            dp[i + 1][j - y + B[i + 1] - x] %= 1000000007LL;
          }
        }
      }
  printf("%lld\n", dp[m][0]);
  return 0;
}
