#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const int MOD = 1000000007;
int N;
int par[MAXN];
int sz[MAXN];
long long A[MAXN];
long long fac[MAXN];
long long C[MAXN][MAXN];
int G[MAXN], numG = 0;
long long dp[MAXN][MAXN];
bool is_sq(long long x) {
  long long lo = 1, hi = MOD;
  while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (mid * mid == x)
      return true;
    else if (mid * mid < x)
      lo = mid + 1;
    else
      hi = mid - 1;
  }
  return false;
}
int find_parent(int x) {
  if (par[x] == x) return x;
  return par[x] = find_parent(par[x]);
}
void merge(int a, int b) {
  a = find_parent(a), b = find_parent(b);
  if (a != b) {
    par[a] = b;
    sz[b] += sz[a];
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> N;
  for (int i = 0; i < N; i++) {
    par[i] = i;
    sz[i] = 1;
  }
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      if (is_sq(A[i] * A[j])) merge(i, j);
  C[0][0] = 1;
  for (int i = 1; i < MAXN; i++) {
    C[i][0] = 1;
    for (int j = 1; j < MAXN; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 0; i < N; i++)
    if (find_parent(i) == i) G[numG++] = sz[i];
  dp[0][0] = 1;
  for (int i = 0, total = 0; i < numG; i++) {
    for (int j = 0; j <= total; j++) {
      if (dp[i][j] == 0) continue;
      for (int k = 1; k <= G[i] && k <= total + 1; k++)
        for (int d = 0; d <= j && d <= k; d++) {
          long long x = C[G[i] - 1][k - 1] *
                        (C[j][d] * C[total + 1 - j][k - d] % MOD) % MOD;
          x = x * fac[G[i]] % MOD;
          dp[i + 1][j - d + G[i] - k] =
              (dp[i + 1][j - d + G[i] - k] + x * dp[i][j] % MOD) % MOD;
        }
    }
    total += G[i];
  }
  cout << dp[numG][0] << "\n";
  return 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;
const int MAXN = 305;
const int MOD = 1000000007;
int N;
int par[MAXN];
int sz[MAXN];
long long A[MAXN];
long long fac[MAXN];
long long C[MAXN][MAXN];
int G[MAXN], numG = 0;
long long dp[MAXN][MAXN];
bool is_sq(long long x) {
  long long lo = 1, hi = MOD;
  while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (mid * mid == x)
      return true;
    else if (mid * mid < x)
      lo = mid + 1;
    else
      hi = mid - 1;
  }
  return false;
}
int find_parent(int x) {
  if (par[x] == x) return x;
  return par[x] = find_parent(par[x]);
}
void merge(int a, int b) {
  a = find_parent(a), b = find_parent(b);
  if (a != b) {
    par[a] = b;
    sz[b] += sz[a];
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin >> N;
  for (int i = 0; i < N; i++) {
    par[i] = i;
    sz[i] = 1;
  }
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      if (is_sq(A[i] * A[j])) merge(i, j);
  C[0][0] = 1;
  for (int i = 1; i < MAXN; i++) {
    C[i][0] = 1;
    for (int j = 1; j < MAXN; j++)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
  }
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
  for (int i = 0; i < N; i++)
    if (find_parent(i) == i) G[numG++] = sz[i];
  dp[0][0] = 1;
  for (int i = 0, total = 0; i < numG; i++) {
    for (int j = 0; j <= total; j++) {
      if (dp[i][j] == 0) continue;
      for (int k = 1; k <= G[i] && k <= total + 1; k++)
        for (int d = 0; d <= j && d <= k; d++) {
          long long x = C[G[i] - 1][k - 1] *
                        (C[j][d] * C[total + 1 - j][k - d] % MOD) % MOD;
          x = x * fac[G[i]] % MOD;
          dp[i + 1][j - d + G[i] - k] =
              (dp[i + 1][j - d + G[i] - k] + x * dp[i][j] % MOD) % MOD;
        }
    }
    total += G[i];
  }
  cout << dp[numG][0] << "\n";
  return 0;
}

```