#include <bits/stdc++.h>
using namespace std;
const int maxn = 310, MOD = int(1e9 + 7);
int fa[maxn], sz[maxn];
int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
bool merge(int u, int v) {
  u = find(u);
  v = find(v);
  if (u == v) {
    return false;
  }
  fa[u] = v;
  sz[v] += sz[u];
  sz[u] = 0;
  return true;
}
bool issqr(long long x) {
  long long t = (long long)sqrt(x);
  while (t * t < x) {
    t++;
  }
  while (t * t > x) {
    t--;
  }
  return t * t == x;
}
int C[maxn << 1][maxn << 1];
int fac[maxn << 1];
void init_C(int n) {
  for (int i = 0; i <= n; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = (int)((long long)fac[i - 1] * i % MOD);
  }
}
int n, a[maxn];
int vec[maxn], vn;
int dp[maxn][maxn];
int main() {
  scanf("%d", &n);
  init_C(n * 2);
  for (int i = 1; i <= n; i++) {
    fa[i] = 0;
    sz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 1; j < i; j++) {
      if (issqr((long long)a[i] * a[j])) {
        merge(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (find(i) == i) {
      vec[++vn] = sz[i];
    }
  }
  dp[1][vec[1]] = fac[vec[1]];
  int cur = vec[1];
  for (int i = 2; i <= vn; i++) {
    for (int j = 0; j <= cur; j++) {
      if (dp[i - 1][j]) {
        int glue = max(0, min(vec[i], j - 1));
        for (int k = 0; k <= glue; k++) {
          int attach = max(0, min(2 * (j - k), vec[i] - k));
          for (int x = 0; x <= attach; x++) {
            int single = vec[i] - k - x;
            dp[i][j - k + single] =
                (int)((dp[i][j - k + single] +
                       (long long)dp[i - 1][j] * C[j - 1][k] % MOD *
                           C[vec[i]][k] % MOD * fac[k] % MOD *
                           C[(j - k) * 2][x] % MOD * C[vec[i] - k][x] % MOD *
                           fac[x] % MOD * C[j - k + single][single] % MOD *
                           fac[single] % MOD) %
                      MOD);
          }
        }
      }
    }
    cur += vec[i];
  }
  printf("%d\n", dp[vn][1]);
  return 0;
}

### Prompt

In CPP, your task is to solve 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 = 310, MOD = int(1e9 + 7);
int fa[maxn], sz[maxn];
int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
bool merge(int u, int v) {
  u = find(u);
  v = find(v);
  if (u == v) {
    return false;
  }
  fa[u] = v;
  sz[v] += sz[u];
  sz[u] = 0;
  return true;
}
bool issqr(long long x) {
  long long t = (long long)sqrt(x);
  while (t * t < x) {
    t++;
  }
  while (t * t > x) {
    t--;
  }
  return t * t == x;
}
int C[maxn << 1][maxn << 1];
int fac[maxn << 1];
void init_C(int n) {
  for (int i = 0; i <= n; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
  }
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = (int)((long long)fac[i - 1] * i % MOD);
  }
}
int n, a[maxn];
int vec[maxn], vn;
int dp[maxn][maxn];
int main() {
  scanf("%d", &n);
  init_C(n * 2);
  for (int i = 1; i <= n; i++) {
    fa[i] = 0;
    sz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    for (int j = 1; j < i; j++) {
      if (issqr((long long)a[i] * a[j])) {
        merge(i, j);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (find(i) == i) {
      vec[++vn] = sz[i];
    }
  }
  dp[1][vec[1]] = fac[vec[1]];
  int cur = vec[1];
  for (int i = 2; i <= vn; i++) {
    for (int j = 0; j <= cur; j++) {
      if (dp[i - 1][j]) {
        int glue = max(0, min(vec[i], j - 1));
        for (int k = 0; k <= glue; k++) {
          int attach = max(0, min(2 * (j - k), vec[i] - k));
          for (int x = 0; x <= attach; x++) {
            int single = vec[i] - k - x;
            dp[i][j - k + single] =
                (int)((dp[i][j - k + single] +
                       (long long)dp[i - 1][j] * C[j - 1][k] % MOD *
                           C[vec[i]][k] % MOD * fac[k] % MOD *
                           C[(j - k) * 2][x] % MOD * C[vec[i] - k][x] % MOD *
                           fac[x] % MOD * C[j - k + single][single] % MOD *
                           fac[single] % MOD) %
                      MOD);
          }
        }
      }
    }
    cur += vec[i];
  }
  printf("%d\n", dp[vn][1]);
  return 0;
}

```