#include <bits/stdc++.h>
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  char ch;
  while (blank(ch = nc()))
    ;
  if (IOerror) return;
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
}
};  // namespace fastIO
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool scan(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
const double pi = 3.14159265358979323846264338327950288L;
using namespace std;
const long long mod = 1000000007;
int n, a[305], num[305], sum[305], cnt;
void gao(int x) {
  int tmp = a[x], ans = 1;
  for (int j = 2; j * j <= tmp; j++)
    if (tmp % j == 0) {
      int cnt = 0;
      while (tmp % j == 0) {
        cnt++;
        tmp /= j;
      }
      if (cnt & 1) ans *= j;
    }
  if (tmp) ans *= tmp;
  a[x] = ans;
}
long long C[305][305], A[305];
void init() {
  A[0] = 1;
  for (int i = 1; i < 305; i++) A[i] = A[i - 1] * i % mod;
  memset(C, 0, sizeof(C));
  C[0][0] = 1;
  C[1][0] = C[1][1] = 1;
  for (int i = 2; i < 305; i++) C[i][0] = 1;
  for (int i = 2; i < 305; i++) {
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
}
long long dp[305][305];
void solve() {
  init();
  memset(dp, 0, sizeof(dp));
  dp[0][num[0] - 1] = A[num[0]];
  for (int i = 1; i < cnt; i++) {
    for (int j = 0; j < sum[i - 1]; j++) {
      int p = num[i];
      for (int k = 1; k <= p; k++) {
        for (int l = 0; l <= min(j, k); l++) {
          dp[i][j - l + p - k] += dp[i - 1][j] * A[p] % mod * C[p - 1][k - 1] %
                                  mod * C[j][l] % mod *
                                  C[sum[i - 1] - j + 1][k - l] % mod;
          dp[i][j - l + p - k] %= mod;
        }
      }
    }
  }
  printf("%lld\n", dp[cnt - 1][0]);
}
int main() {
  while (cin >> n) {
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      gao(i);
    }
    sort(a, a + n);
    int tmp = 0;
    cnt = 0;
    for (int i = 0; i < n; i++) {
      if (!i || a[i] == a[i - 1])
        tmp++;
      else {
        num[cnt++] = tmp;
        tmp = 1;
      }
    }
    num[cnt++] = tmp;
    for (int i = 0; i < cnt; i++) sum[i] = (!i ? num[i] : num[i] + sum[i - 1]);
    solve();
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

A year ago on the bench in public park Leha found an array of n numbers. Leha believes that permutation p is right if for all 1 ≤ i < n condition, that api·api + 1 is not perfect square, holds. Leha wants to find number of right permutations modulo 109 + 7.

Input

First line of input data contains single integer n (1 ≤ n ≤ 300) — length of the array.

Next line contains n integers a1, a2, ... , an (1 ≤ ai ≤ 109) — found array.

Output

Output single integer — number of right permutations modulo 109 + 7.

Examples

Input

3
1 2 4


Output

2


Input

7
5 2 4 2 4 1 1


Output

144

Note

For first example:

[1, 2, 4] — right permutation, because 2 and 8 are not perfect squares.

[1, 4, 2] — wrong permutation, because 4 is square of 2.

[2, 1, 4] — wrong permutation, because 4 is square of 2.

[2, 4, 1] — wrong permutation, because 4 is square of 2.

[4, 1, 2] — wrong permutation, because 4 is square of 2.

[4, 2, 1] — right permutation, because 8 and 2 are not perfect squares.

### Response

```cpp
#include <bits/stdc++.h>
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  char ch;
  while (blank(ch = nc()))
    ;
  if (IOerror) return;
  for (x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0')
    ;
}
};  // namespace fastIO
template <class T>
inline T lowbit(T x) {
  return x & (-x);
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline bool scan(T &ret) {
  char c;
  int sgn;
  if (c = getchar(), c == EOF) return 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  sgn = (c == '-') ? -1 : 1;
  ret = (c == '-') ? 0 : (c - '0');
  while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
  ret *= sgn;
  return 1;
}
const double pi = 3.14159265358979323846264338327950288L;
using namespace std;
const long long mod = 1000000007;
int n, a[305], num[305], sum[305], cnt;
void gao(int x) {
  int tmp = a[x], ans = 1;
  for (int j = 2; j * j <= tmp; j++)
    if (tmp % j == 0) {
      int cnt = 0;
      while (tmp % j == 0) {
        cnt++;
        tmp /= j;
      }
      if (cnt & 1) ans *= j;
    }
  if (tmp) ans *= tmp;
  a[x] = ans;
}
long long C[305][305], A[305];
void init() {
  A[0] = 1;
  for (int i = 1; i < 305; i++) A[i] = A[i - 1] * i % mod;
  memset(C, 0, sizeof(C));
  C[0][0] = 1;
  C[1][0] = C[1][1] = 1;
  for (int i = 2; i < 305; i++) C[i][0] = 1;
  for (int i = 2; i < 305; i++) {
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
}
long long dp[305][305];
void solve() {
  init();
  memset(dp, 0, sizeof(dp));
  dp[0][num[0] - 1] = A[num[0]];
  for (int i = 1; i < cnt; i++) {
    for (int j = 0; j < sum[i - 1]; j++) {
      int p = num[i];
      for (int k = 1; k <= p; k++) {
        for (int l = 0; l <= min(j, k); l++) {
          dp[i][j - l + p - k] += dp[i - 1][j] * A[p] % mod * C[p - 1][k - 1] %
                                  mod * C[j][l] % mod *
                                  C[sum[i - 1] - j + 1][k - l] % mod;
          dp[i][j - l + p - k] %= mod;
        }
      }
    }
  }
  printf("%lld\n", dp[cnt - 1][0]);
}
int main() {
  while (cin >> n) {
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      gao(i);
    }
    sort(a, a + n);
    int tmp = 0;
    cnt = 0;
    for (int i = 0; i < n; i++) {
      if (!i || a[i] == a[i - 1])
        tmp++;
      else {
        num[cnt++] = tmp;
        tmp = 1;
      }
    }
    num[cnt++] = tmp;
    for (int i = 0; i < cnt; i++) sum[i] = (!i ? num[i] : num[i] + sum[i - 1]);
    solve();
  }
  return 0;
}

```