#include <bits/stdc++.h>
using namespace std;
int num[305];
int cnt[305], len = 0;
long long dp[305][305], a[305], c[305][305];
int main() {
  int n, x, y;
  scanf("%d", &n);
  a[0] = 1;
  c[0][0] = 1;
  for (int i = 0; i < n; i++) {
    c[i + 1][0] = 1;
    for (int j = 1; j <= i + 1; j++)
      c[i + 1][j] = (c[i][j - 1] + c[i][j]) % 1000000007;
    a[i + 1] = (a[i] * (i + 1)) % 1000000007;
    scanf("%d", &x);
    num[i] = 1;
    for (int j = 2; j * j <= x; j++) {
      y = 0;
      while (x % j == 0) {
        x /= j;
        y++;
      }
      if (y % 2) num[i] *= j;
    }
    if (x > 1) num[i] *= x;
  }
  sort(num, num + n);
  x = 1;
  for (int i = 1; i < n; i++) {
    if (num[i] != num[i - 1]) {
      cnt[len++] = x;
      x = 1;
    } else
      x++;
  }
  cnt[len++] = x;
  dp[0][cnt[0] - 1] = 1;
  x = cnt[0];
  for (int i = 1; i < len; i++) {
    for (int j = 0; j <= n; j++) {
      if (dp[i - 1][j]) {
        for (int k = 1; k <= cnt[i]; k++)
          for (int l = 0; l <= k && l <= j; l++)
            dp[i][j - l + cnt[i] - k] =
                (dp[i][j - l + cnt[i] - k] +
                 (((((dp[i - 1][j] * c[cnt[i] - 1][k - 1]) % 1000000007) *
                    c[j][l]) %
                   1000000007) *
                  c[x + 1 - j][k - l]) %
                     1000000007) %
                1000000007;
      }
    }
    x += cnt[i];
  }
  for (int i = 0; i < len; i++)
    dp[len - 1][0] = (dp[len - 1][0] * a[cnt[i]]) % 1000000007;
  printf("%lld\n", dp[len - 1][0]);
  return 0;
}
