#include <bits/stdc++.h>
using namespace std;
const long long M = 1000000007;
long long c[300 + 1][300 + 1];
long long C(int x, int y) {
  if (x >= y)
    return c[x][y];
  else
    return 0;
}
int main() {
  int n, a[300];
  long long dp[2][300], fact[300 + 1];
  scanf("%d", &n);
  fact[0] = 1;
  for (int i = 1; i <= n; ++i) fact[i] = (fact[i - 1] * (long long)i) % M;
  c[0][0] = 1;
  for (int i = 0; i < n; ++i) {
    c[i + 1][0] = 1;
    c[i + 1][i + 1] = 1;
    for (int j = 1; j <= i; ++j) c[i + 1][j] = (c[i][j - 1] + c[i][j]) % M;
  }
  for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
  vector<int> v;
  bool f[300];
  fill(f, f + n, false);
  for (int i = 0; i < n; ++i)
    if (!f[i]) {
      f[i] = true;
      v.push_back(1);
      for (int j = i + 1; j < n; ++j)
        if (((long long)sqrt((long long)a[i] * (long long)a[j])) *
                ((long long)sqrt((long long)a[i] * (long long)a[j])) ==
            (long long)a[i] * (long long)a[j]) {
          f[j] = true;
          ++*(v.rbegin());
        }
    }
  int s = v[0];
  for (int j = 0; j < s - 1; ++j) dp[0][j] = 0;
  dp[0][s - 1] = fact[s];
  for (int i = 0; i < v.size() - 1; ++i) {
    fill(dp[(i + 1) % 2], dp[(i + 1) % 2] + (s + v[i + 1]), 0);
    for (int j = 0; j < s - i; ++j) {
      if (dp[i % 2][j] == 0) continue;
      for (int g = 1; g <= min(v[i + 1], s + 1); ++g)
        for (int d = 0; d <= min(j, g); ++d) {
          dp[(i + 1) % 2][j - d + v[i + 1] - g] +=
              ((((((((dp[i % 2][j] * fact[v[i + 1]]) % M) * c[j][d]) % M) *
                  C(s + 1 - j, g - d)) %
                 M) *
                c[v[i + 1] - 1][g - 1]) %
               M);
          dp[(i + 1) % 2][j - d + v[i + 1] - g] %= M;
        }
    }
    s += v[i + 1];
  }
  cout << dp[(v.size() - 1) % 2][0] << endl;
}
