#include <bits/stdc++.h>
using namespace std;
#pragma warning(disable : 4996)
const int maxn = 305;
const int mod = 1000000007;
int a[maxn];
int tot;
int Array[maxn];
bool vis[maxn];
bool check(long long a) {
  long long l = 1, r = 1e9;
  long long mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (mid * mid >= a)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l * l == a;
}
long long C[maxn][maxn];
long long fact[maxn];
void init() {
  C[0][0] = 1;
  C[1][0] = 1;
  C[1][1] = 1;
  for (int i = 2; i <= 300; i++) C[i][0] = 1;
  for (int i = 2; i <= 300; i++)
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  fact[0] = 1;
  for (int i = 1; i <= 300; i++) fact[i] = fact[i - 1] * i % mod;
}
int dp[maxn][maxn];
void solve() {
  int cnt = Array[0];
  dp[0][cnt - 1] = 1;
  for (int i = 1; i < tot; i++) {
    for (int j = 0; j < cnt; j++) {
      for (int k = 0; k < Array[i]; k++) {
        for (int m = 0; m <= min(j, k + 1); m++) {
          dp[i][j + Array[i] - 1 - k - m] =
              (dp[i][j + Array[i] - 1 - k - m] +
               1LL * dp[i - 1][j] * C[Array[i] - 1][k] % mod * C[j][m] % mod *
                   C[cnt - 1 - j + 2][k + 1 - m] % mod) %
              mod;
        }
      }
    }
    cnt += Array[i];
  }
  long long ans = dp[tot - 1][0];
  for (int i = 0; i < tot; i++) {
    ans = ans * fact[Array[i]];
    ans %= mod;
  }
  cout << ans << endl;
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      for (int j = i; j <= n; j++) {
        if (check(1LL * a[i] * a[j])) {
          vis[j] = 1;
          Array[tot]++;
        }
      }
      tot++;
    }
  init();
  solve();
}

### Prompt

Develop a solution in Cpp 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;
#pragma warning(disable : 4996)
const int maxn = 305;
const int mod = 1000000007;
int a[maxn];
int tot;
int Array[maxn];
bool vis[maxn];
bool check(long long a) {
  long long l = 1, r = 1e9;
  long long mid;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (mid * mid >= a)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l * l == a;
}
long long C[maxn][maxn];
long long fact[maxn];
void init() {
  C[0][0] = 1;
  C[1][0] = 1;
  C[1][1] = 1;
  for (int i = 2; i <= 300; i++) C[i][0] = 1;
  for (int i = 2; i <= 300; i++)
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  fact[0] = 1;
  for (int i = 1; i <= 300; i++) fact[i] = fact[i - 1] * i % mod;
}
int dp[maxn][maxn];
void solve() {
  int cnt = Array[0];
  dp[0][cnt - 1] = 1;
  for (int i = 1; i < tot; i++) {
    for (int j = 0; j < cnt; j++) {
      for (int k = 0; k < Array[i]; k++) {
        for (int m = 0; m <= min(j, k + 1); m++) {
          dp[i][j + Array[i] - 1 - k - m] =
              (dp[i][j + Array[i] - 1 - k - m] +
               1LL * dp[i - 1][j] * C[Array[i] - 1][k] % mod * C[j][m] % mod *
                   C[cnt - 1 - j + 2][k + 1 - m] % mod) %
              mod;
        }
      }
    }
    cnt += Array[i];
  }
  long long ans = dp[tot - 1][0];
  for (int i = 0; i < tot; i++) {
    ans = ans * fact[Array[i]];
    ans %= mod;
  }
  cout << ans << endl;
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      for (int j = i; j <= n; j++) {
        if (check(1LL * a[i] * a[j])) {
          vis[j] = 1;
          Array[tot]++;
        }
      }
      tot++;
    }
  init();
  solve();
}

```