#include <bits/stdc++.h>
using namespace std;
const int N = 310;
const int mod = 1e9 + 7;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
int qpow(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
int C[N][N], fac[N], ifac[N], f[N][N], A[N], B[N], fa[N], a[N], siz[N], tt, n;
int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
bool is_sqr(long long n) {
  int rt = sqrtl(n) + 10;
  while (1ll * rt * rt > n) --rt;
  return 1ll * rt * rt == n;
}
void mul() {
  static int new_A[N];
  memset(new_A, 0, sizeof(new_A));
  for (int i = 0; i < N; i++)
    for (int j = 0; i + j < N; j++)
      new_A[i + j] = (new_A[i + j] + 1ll * A[i] * B[j]) % mod;
  for (int i = 0; i < N; i++) A[i] = new_A[i];
}
int main() {
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[N - 1] = qpow(fac[N - 1], mod - 2);
  for (int i = N - 1; i; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
  f[0][0] = 1;
  for (int i = 1; i < N; i++)
    for (int j = 1; j <= i; j++)
      for (int k = 1; k <= i; k++)
        f[i][j] =
            (f[i][j] + 1ll * C[i][k] * fac[k] % mod * f[i - k][j - 1]) % mod;
  cin >> n;
  for (int i = 1; i <= n; i++) fa[i] = i, a[i] = gi();
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (is_sqr(1ll * a[i] * a[j])) fa[getf(i)] = getf(j);
  for (int i = 1; i <= n; i++) ++siz[getf(i)];
  for (int i = 1; i <= n; i++)
    if (getf(i) == i) siz[++tt] = siz[i];
  A[0] = 1;
  for (int i = 1; i <= tt; i++) {
    memset(B, 0, sizeof(B));
    for (int j = 1; j <= siz[i]; j++)
      B[j] = 1ll * ifac[j] * (((siz[i] - j) & 1) ? mod - 1 : 1) % mod *
             f[siz[i]][j] % mod;
    mul();
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans = (ans + 1ll * A[i] * fac[i]) % mod;
  cout << 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 N = 310;
const int mod = 1e9 + 7;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
int qpow(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    b >>= 1;
  }
  return ret;
}
int C[N][N], fac[N], ifac[N], f[N][N], A[N], B[N], fa[N], a[N], siz[N], tt, n;
int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
bool is_sqr(long long n) {
  int rt = sqrtl(n) + 10;
  while (1ll * rt * rt > n) --rt;
  return 1ll * rt * rt == n;
}
void mul() {
  static int new_A[N];
  memset(new_A, 0, sizeof(new_A));
  for (int i = 0; i < N; i++)
    for (int j = 0; i + j < N; j++)
      new_A[i + j] = (new_A[i + j] + 1ll * A[i] * B[j]) % mod;
  for (int i = 0; i < N; i++) A[i] = new_A[i];
}
int main() {
  for (int i = 0; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
  }
  fac[0] = 1;
  for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
  ifac[N - 1] = qpow(fac[N - 1], mod - 2);
  for (int i = N - 1; i; i--) ifac[i - 1] = 1ll * ifac[i] * i % mod;
  f[0][0] = 1;
  for (int i = 1; i < N; i++)
    for (int j = 1; j <= i; j++)
      for (int k = 1; k <= i; k++)
        f[i][j] =
            (f[i][j] + 1ll * C[i][k] * fac[k] % mod * f[i - k][j - 1]) % mod;
  cin >> n;
  for (int i = 1; i <= n; i++) fa[i] = i, a[i] = gi();
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (is_sqr(1ll * a[i] * a[j])) fa[getf(i)] = getf(j);
  for (int i = 1; i <= n; i++) ++siz[getf(i)];
  for (int i = 1; i <= n; i++)
    if (getf(i) == i) siz[++tt] = siz[i];
  A[0] = 1;
  for (int i = 1; i <= tt; i++) {
    memset(B, 0, sizeof(B));
    for (int j = 1; j <= siz[i]; j++)
      B[j] = 1ll * ifac[j] * (((siz[i] - j) & 1) ? mod - 1 : 1) % mod *
             f[siz[i]][j] % mod;
    mul();
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) ans = (ans + 1ll * A[i] * fac[i]) % mod;
  cout << ans;
  return 0;
}

```