#include <bits/stdc++.h>
using namespace std;
int read() {
  int n = 0;
  bool b = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') b = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return b ? -n : n;
}
const int N = 307, mod = 1e9 + 7;
int a[N], f[2][N][N], cnt, n;
void div(int &x) {
  for (int i = 2; i <= sqrt(x); ++i) {
    while (!(x % (i * i))) x /= (i * i);
  }
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), div(a[i]);
  sort(a + 1, a + n + 1);
  f[0][0][0] = 1;
  int x = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] != a[i - 1]) {
      for (int j = 0; j <= i; ++j)
        for (int k = 1; k <= cnt; ++k) {
          f[x ^ 1][j][0] = (f[x ^ 1][j][0] + f[x ^ 1][j][k] % mod) % mod;
          f[x ^ 1][j][k] = 0;
        }
      cnt = 0;
    }
    for (int j = 0; j <= i; ++j)
      for (int k = 0; k <= min(cnt, j); ++k) {
        if (j && k)
          f[x][j][k] =
              (0ll + f[x][j][k] +
               (1ll * f[x ^ 1][j - 1][k - 1] * (2 * cnt - k + 1) % mod) % mod) %
              mod;
        f[x][j][k] = (0ll + f[x][j][k] +
                      (1ll * f[x ^ 1][j + 1][k] * (j + 1 - k) % mod)) %
                     mod;
        f[x][j][k] = (0ll + f[x][j][k] +
                      (1ll * f[x ^ 1][j][k] *
                       (0ll + i - (2 * cnt - k) - (j - k)) % mod)) %
                     mod;
      }
    x ^= 1;
    ++cnt;
    memset(f[x], 0, sizeof(f[x]));
  }
  printf("%d\n", f[x ^ 1][0][0]);
}

### Prompt

Please provide a Cpp coded solution 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>
using namespace std;
int read() {
  int n = 0;
  bool b = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') b = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    n = (n << 1) + (n << 3) + (c ^ 48);
    c = getchar();
  }
  return b ? -n : n;
}
const int N = 307, mod = 1e9 + 7;
int a[N], f[2][N][N], cnt, n;
void div(int &x) {
  for (int i = 2; i <= sqrt(x); ++i) {
    while (!(x % (i * i))) x /= (i * i);
  }
}
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) a[i] = read(), div(a[i]);
  sort(a + 1, a + n + 1);
  f[0][0][0] = 1;
  int x = 0;
  for (int i = 1; i <= n; ++i) {
    if (a[i] != a[i - 1]) {
      for (int j = 0; j <= i; ++j)
        for (int k = 1; k <= cnt; ++k) {
          f[x ^ 1][j][0] = (f[x ^ 1][j][0] + f[x ^ 1][j][k] % mod) % mod;
          f[x ^ 1][j][k] = 0;
        }
      cnt = 0;
    }
    for (int j = 0; j <= i; ++j)
      for (int k = 0; k <= min(cnt, j); ++k) {
        if (j && k)
          f[x][j][k] =
              (0ll + f[x][j][k] +
               (1ll * f[x ^ 1][j - 1][k - 1] * (2 * cnt - k + 1) % mod) % mod) %
              mod;
        f[x][j][k] = (0ll + f[x][j][k] +
                      (1ll * f[x ^ 1][j + 1][k] * (j + 1 - k) % mod)) %
                     mod;
        f[x][j][k] = (0ll + f[x][j][k] +
                      (1ll * f[x ^ 1][j][k] *
                       (0ll + i - (2 * cnt - k) - (j - k)) % mod)) %
                     mod;
      }
    x ^= 1;
    ++cnt;
    memset(f[x], 0, sizeof(f[x]));
  }
  printf("%d\n", f[x ^ 1][0][0]);
}

```