#include <bits/stdc++.h>
using namespace std;
long long dp[310][310], parent[310], arr[310], cmb[310][310], M = 1e9 + 7,
                                                              fact[310];
vector<long long> grp[310];
void pre() {
  long long i, j;
  fact[0] = 1;
  for (i = 1; i <= 300; i++) fact[i] = fact[i - 1] * i, fact[i] %= M;
  cmb[0][0] = cmb[1][0] = cmb[1][1] = 1;
  for (i = 2; i <= 300; i++) {
    cmb[i][0] = 1;
    for (j = 1; j <= i; j++) {
      cmb[i][j] = cmb[i - 1][j] + cmb[i - 1][j - 1];
      cmb[i][j] %= M;
    }
  }
}
long long fexpo(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b % 2) {
      res *= a;
      res %= M;
    }
    a *= a;
    a %= M;
    b /= 2;
  }
  return res;
}
int main() {
  long long n, m, i, j, k, l;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  pre();
  cin >> n;
  for (i = 1; i <= n; i++) cin >> arr[i];
  for (i = 1; i <= n; i++) parent[i] = i;
  long long K = 1;
  for (i = 1; i <= n; i++) {
    if (parent[i] != i) continue;
    grp[K].push_back(i);
    for (j = i + 1; j <= n; j++) {
      long long p = sqrt(arr[i] * arr[j]);
      if (p * p == arr[i] * arr[j]) parent[j] = i, grp[K].push_back(j);
    }
    K++;
  }
  dp[0][0] = 1;
  for (i = 1; i <= n + 1; i++) dp[0][i] = 0;
  long long sum = 0;
  for (i = 1; i < K; i++) {
    sort(grp[i].begin(), grp[i].end());
    long long op = grp[i].size(), x, distinct = 1, res = 1;
    for (j = 1; j < op; j++)
      if (grp[i][j] == grp[i][j - 1])
        distinct++;
      else {
        res = res * fact[distinct];
        distinct = 1;
        res %= M;
      }
    res = res * fact[distinct];
    distinct = 1;
    res %= M;
    for (x = 0; x <= sum + 1; x++) {
      for (j = 0; j <= min(x, op); j++) {
        for (k = 0; k <= min(sum + 1 - x, op - j); k++) {
          long long opp = cmb[x][j] * cmb[sum + 1 - x][k];
          opp %= M;
          long long opp2 = cmb[op - 1][j + k - 1] * fact[op];
          opp2 %= M;
          opp *= (opp2 * fexpo(res, M - 2)) % M;
          opp %= M;
          dp[i][x - j + op - j - k] += (dp[i - 1][x] * opp);
          dp[i][x - j + op - j - k] %= M;
        }
      }
    }
    sum += op;
  }
  cout << dp[K - 1][0] << '\n';
  return 0;
}
