#include <bits/stdc++.h>
using namespace std;
const int Maxn = 310;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const double pi = acos(-1.0);
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10ll + ch - '0', ch = getchar();
  return x * f;
}
void upd(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int n, a[Maxn], m = 0, cnt[Maxn], f[Maxn][Maxn], C[Maxn << 1][Maxn << 1],
                fac[Maxn], sum[Maxn];
void init() {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % mod;
  for (int i = 0; i <= n * 2; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
}
int main() {
  n = read();
  init();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
    }
  }
  sort(a + 1, a + 1 + n);
  a[0] = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] != a[i - 1])
      cnt[++m] = 1;
    else
      cnt[m]++;
  }
  sum[0] = 0;
  for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + cnt[i];
  f[0][0] = 1;
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      if (f[i][j]) {
        int t = f[i][j];
        for (int l = 1; l <= min(cnt[i + 1], sum[i] + 1); l++)
          for (int k = 0; k <= min(l, j); k++)
            upd(f[i + 1][j - k + cnt[i + 1] - l],
                (long long)t * fac[cnt[i + 1]] % mod *
                    C[cnt[i + 1] - 1][l - 1] % mod * C[j][k] % mod *
                    C[sum[i] + 1 - j][l - k] % mod);
      }
  printf("%d", f[m][0]);
}

### Prompt

Generate a CPP solution to 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;
const int mod = 1e9 + 7;
const int inf = 2147483647;
const double pi = acos(-1.0);
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10ll + ch - '0', ch = getchar();
  return x * f;
}
void upd(int& x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int n, a[Maxn], m = 0, cnt[Maxn], f[Maxn][Maxn], C[Maxn << 1][Maxn << 1],
                fac[Maxn], sum[Maxn];
void init() {
  fac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = (long long)fac[i - 1] * i % mod;
  for (int i = 0; i <= n * 2; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
}
int main() {
  n = read();
  init();
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    for (int j = 2; j * j <= a[i]; j++) {
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
    }
  }
  sort(a + 1, a + 1 + n);
  a[0] = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] != a[i - 1])
      cnt[++m] = 1;
    else
      cnt[m]++;
  }
  sum[0] = 0;
  for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + cnt[i];
  f[0][0] = 1;
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      if (f[i][j]) {
        int t = f[i][j];
        for (int l = 1; l <= min(cnt[i + 1], sum[i] + 1); l++)
          for (int k = 0; k <= min(l, j); k++)
            upd(f[i + 1][j - k + cnt[i + 1] - l],
                (long long)t * fac[cnt[i + 1]] % mod *
                    C[cnt[i + 1] - 1][l - 1] % mod * C[j][k] % mod *
                    C[sum[i] + 1 - j][l - k] % mod);
      }
  printf("%d", f[m][0]);
}

```