#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int maxn = 305;
int n, cnt[305], pre[305], sz;
long long a[maxn], C[maxn][maxn], dp[maxn][maxn], fac[maxn];
bool vis[305];
inline void init() {
  C[0][0] = fac[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    C[i][0] = 1;
    fac[i] = fac[i - 1] * i % mod;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
}
inline long long check(long long x) {
  long long left = 1, right = (long long)sqrt(x) + 100, res = 1;
  while (left <= right) {
    long long mid = (left + right) >> 1;
    if (mid * mid <= x) {
      res = mid;
      left = mid + 1;
    } else
      right = mid - 1;
  }
  return res * res == x;
}
inline void update(long long &a, long long b) { a = (a + b) % mod; }
int main() {
  init();
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%I64d", &a[i]);
  for (int i = 0; i < n; ++i)
    if (!vis[i]) {
      for (int j = i; j < n; ++j)
        if (!vis[j]) {
          if (check(a[i] * a[j])) {
            ++cnt[sz];
            vis[j] = 1;
          }
        }
      ++sz;
    }
  for (int i = 0; i < sz; ++i) pre[i + 1] = pre[i] + cnt[i];
  dp[0][0] = 1;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j <= pre[i]; ++j)
      if (dp[i][j])
        for (int k = 1; k <= cnt[i]; ++k)
          for (int l = 0; l <= min(j, k); ++l)
            update(dp[i + 1][j + cnt[i] - k - l],
                   fac[cnt[i]] * C[pre[i] + 1 - j][k - l] % mod * C[j][l] %
                       mod * C[cnt[i] - 1][k - 1] % mod * dp[i][j] % mod);
  printf("%I64d\n", dp[sz][0]);
  return 0;
}

### Prompt

In cpp, your task is to solve 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 long long mod = 1e9 + 7;
const int maxn = 305;
int n, cnt[305], pre[305], sz;
long long a[maxn], C[maxn][maxn], dp[maxn][maxn], fac[maxn];
bool vis[305];
inline void init() {
  C[0][0] = fac[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    C[i][0] = 1;
    fac[i] = fac[i - 1] * i % mod;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
}
inline long long check(long long x) {
  long long left = 1, right = (long long)sqrt(x) + 100, res = 1;
  while (left <= right) {
    long long mid = (left + right) >> 1;
    if (mid * mid <= x) {
      res = mid;
      left = mid + 1;
    } else
      right = mid - 1;
  }
  return res * res == x;
}
inline void update(long long &a, long long b) { a = (a + b) % mod; }
int main() {
  init();
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%I64d", &a[i]);
  for (int i = 0; i < n; ++i)
    if (!vis[i]) {
      for (int j = i; j < n; ++j)
        if (!vis[j]) {
          if (check(a[i] * a[j])) {
            ++cnt[sz];
            vis[j] = 1;
          }
        }
      ++sz;
    }
  for (int i = 0; i < sz; ++i) pre[i + 1] = pre[i] + cnt[i];
  dp[0][0] = 1;
  for (int i = 0; i < sz; ++i)
    for (int j = 0; j <= pre[i]; ++j)
      if (dp[i][j])
        for (int k = 1; k <= cnt[i]; ++k)
          for (int l = 0; l <= min(j, k); ++l)
            update(dp[i + 1][j + cnt[i] - k - l],
                   fac[cnt[i]] * C[pre[i] + 1 - j][k - l] % mod * C[j][l] %
                       mod * C[cnt[i] - 1][k - 1] % mod * dp[i][j] % mod);
  printf("%I64d\n", dp[sz][0]);
  return 0;
}

```