#include <bits/stdc++.h>
using namespace std;
const int maxn = 600 + 7, N = 600;
const long long MOD = (1e9) + 7, B = (1e9) + 1;
int n, Fa[maxn], id[maxn], v[maxn], vs, r, k, sum[maxn];
long long a[maxn], F[maxn][maxn], C[maxn][maxn], ans;
int find(int k) { return (Fa[k] == k) ? (k) : (Fa[k] = find(Fa[k])); }
bool check(long long p) {
  long long L = 1, R = B, mid;
  while (L < (R - 1)) {
    mid = (L + R) >> 1;
    if ((mid * mid) > p)
      R = mid - 1;
    else
      L = mid;
  }
  if ((L * L) == p) return true;
  if ((R * R) == p) return true;
  return false;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) Fa[i] = i;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
    for (int j = 1; j <= i - 1; j++)
      if (check(a[i] * a[j])) {
        Fa[i] = find(j);
        break;
      }
  }
  for (int i = 1; i <= n; i++) {
    k = find(i);
    if (!id[k]) id[k] = ++vs;
    ++v[id[k]];
  }
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + v[i];
  for (int i = 0; i <= N; i++) C[i][0] = C[i][i] = 1;
  for (int i = 2; i <= N; i++)
    for (int j = 1; j <= i - 1; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  F[1][v[1] - 1] = 1;
  for (int i = 1; i <= vs - 1; i++) {
    for (int j = 0; j <= sum[i] - 1; j++) {
      if (!F[i][j]) continue;
      for (int l = 1; l <= v[i + 1]; l++) {
        r = min(l, j);
        for (int K = 0; K <= r; K++) {
          F[i + 1][j - l + v[i + 1] - K] +=
              (((((F[i][j] * C[v[i + 1] - 1][l - 1]) % MOD) * C[j][K]) % MOD) *
               C[sum[i] + 1 - j][l - K]) %
              MOD;
          if (F[i + 1][j - l + v[i + 1] - K] >= MOD)
            F[i + 1][j - l + v[i + 1] - K] -= MOD;
        }
      }
    }
  }
  ans = F[vs][0];
  for (int i = 1; i <= vs; i++)
    for (int j = 2; j <= v[i]; j++) ans = (ans * (long long)(j)) % MOD;
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

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>
using namespace std;
const int maxn = 600 + 7, N = 600;
const long long MOD = (1e9) + 7, B = (1e9) + 1;
int n, Fa[maxn], id[maxn], v[maxn], vs, r, k, sum[maxn];
long long a[maxn], F[maxn][maxn], C[maxn][maxn], ans;
int find(int k) { return (Fa[k] == k) ? (k) : (Fa[k] = find(Fa[k])); }
bool check(long long p) {
  long long L = 1, R = B, mid;
  while (L < (R - 1)) {
    mid = (L + R) >> 1;
    if ((mid * mid) > p)
      R = mid - 1;
    else
      L = mid;
  }
  if ((L * L) == p) return true;
  if ((R * R) == p) return true;
  return false;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) Fa[i] = i;
  for (int i = 1; i <= n; i++) {
    scanf("%I64d", &a[i]);
    for (int j = 1; j <= i - 1; j++)
      if (check(a[i] * a[j])) {
        Fa[i] = find(j);
        break;
      }
  }
  for (int i = 1; i <= n; i++) {
    k = find(i);
    if (!id[k]) id[k] = ++vs;
    ++v[id[k]];
  }
  for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + v[i];
  for (int i = 0; i <= N; i++) C[i][0] = C[i][i] = 1;
  for (int i = 2; i <= N; i++)
    for (int j = 1; j <= i - 1; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  F[1][v[1] - 1] = 1;
  for (int i = 1; i <= vs - 1; i++) {
    for (int j = 0; j <= sum[i] - 1; j++) {
      if (!F[i][j]) continue;
      for (int l = 1; l <= v[i + 1]; l++) {
        r = min(l, j);
        for (int K = 0; K <= r; K++) {
          F[i + 1][j - l + v[i + 1] - K] +=
              (((((F[i][j] * C[v[i + 1] - 1][l - 1]) % MOD) * C[j][K]) % MOD) *
               C[sum[i] + 1 - j][l - K]) %
              MOD;
          if (F[i + 1][j - l + v[i + 1] - K] >= MOD)
            F[i + 1][j - l + v[i + 1] - K] -= MOD;
        }
      }
    }
  }
  ans = F[vs][0];
  for (int i = 1; i <= vs; i++)
    for (int j = 2; j <= v[i]; j++) ans = (ans * (long long)(j)) % MOD;
  printf("%I64d\n", ans);
  return 0;
}

```