#include <bits/stdc++.h>
using namespace std;
const int N = 310, MOD = 1000000007;
long long num[N], c[N][N];
long long dp[N][N], a[N];
int tmp, n, tot, example[N];
bool key;
bool ask(int x, int y) {
  long long re = 1;
  re *= x;
  re *= y;
  long long f = sqrt(re);
  if (f * f == re) return 1;
  return 0;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> tmp;
    key = 1;
    for (int j = 1; j <= tot; j++) {
      if (ask(tmp, example[j])) {
        num[j]++;
        key = 0;
        break;
      }
    }
    if (key) {
      num[++tot] = 1;
      example[tot] = tmp;
    }
  }
  for (int i = 0; i <= n; i++) c[i][0] = 1;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
      c[i][j] %= MOD;
    }
  int m = 0;
  a[1] = 1;
  for (int i = 2; i <= n; i++) {
    a[i] = a[i - 1] * i;
    a[i] %= MOD;
  }
  dp[0][0] = 1;
  long long temp, temp1;
  for (int i = 1; i <= tot; i++) {
    for (int j = 0; j < n && j <= m + 1; j++) {
      if (dp[i - 1][j] == 0) continue;
      for (int k = 0; k < num[i]; k++) {
        temp = dp[i - 1][j] * c[num[i] - 1][k];
        temp %= MOD;
        for (int p = 0; p <= k + 1 && p <= j + num[i] - 1 - k; p++) {
          temp1 = temp * c[j][p];
          temp1 %= MOD;
          dp[i][j + num[i] - 1 - k - p] +=
              (temp1 * c[m + 1 - j][k + 1 - p]) % MOD;
          dp[i][j + num[i] - 1 - k - p] %= MOD;
        }
      }
    }
    m += num[i];
  }
  for (int i = 1; i <= tot; i++) {
    dp[tot][0] *= a[num[i]];
    dp[tot][0] %= MOD;
  }
  cout << dp[tot][0] << endl;
  return 0;
}
