#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long dp[500][500];
long long C[500][500];
long long fact[500];
int n;
long long cnt[500];
int sz = 0;
long long a[500];
int vis[500];
int check(long long x) {
  long long st = 1, ed = 1000000000;
  while (st < ed) {
    long long mid = (st + ed) >> 1;
    if (mid * mid == x) {
      st = ed = mid;
    } else if (mid * mid < x) {
      st = mid + 1;
    } else {
      ed = mid - 1;
    }
  }
  return st * st == x;
}
void init() {
  C[0][0] = 1;
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
  for (int i = 1; i <= n; i++) {
    fact[i] = (i * fact[i - 1]) % mod;
  }
}
void solve() {
  dp[0][cnt[0] - 1] = 1;
  int lim = cnt[0];
  for (int i = 1; i < sz; i++) {
    for (int j = 0; j < lim; j++) {
      for (int k = 1; k <= cnt[i]; k++) {
        for (int m = 0; m <= min(j, k); m++) {
          dp[i][j + cnt[i] - k - m] =
              (dp[i][j + cnt[i] - k - m] +
               dp[i - 1][j] * C[cnt[i] - 1][k - 1] % mod * C[j][m] % mod *
                   C[lim - 1 - j + 2][k - m] % mod) %
              mod;
        }
      }
    }
    lim += cnt[i];
  }
  long long ans = dp[sz - 1][0];
  for (int i = 0; i < sz; i++) {
    ans = ans * fact[cnt[i]] % mod;
  }
  printf("%I64d\n", ans);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a[i]);
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    for (int j = i; j < n; j++) {
      if (check((long long)a[i] * a[j])) {
        cnt[sz]++;
        vis[j] = 1;
      }
    }
    sz++;
  }
  init();
  solve();
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 mod = 1e9 + 7;
long long dp[500][500];
long long C[500][500];
long long fact[500];
int n;
long long cnt[500];
int sz = 0;
long long a[500];
int vis[500];
int check(long long x) {
  long long st = 1, ed = 1000000000;
  while (st < ed) {
    long long mid = (st + ed) >> 1;
    if (mid * mid == x) {
      st = ed = mid;
    } else if (mid * mid < x) {
      st = mid + 1;
    } else {
      ed = mid - 1;
    }
  }
  return st * st == x;
}
void init() {
  C[0][0] = 1;
  fact[0] = 1;
  for (int i = 1; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
  for (int i = 1; i <= n; i++) {
    fact[i] = (i * fact[i - 1]) % mod;
  }
}
void solve() {
  dp[0][cnt[0] - 1] = 1;
  int lim = cnt[0];
  for (int i = 1; i < sz; i++) {
    for (int j = 0; j < lim; j++) {
      for (int k = 1; k <= cnt[i]; k++) {
        for (int m = 0; m <= min(j, k); m++) {
          dp[i][j + cnt[i] - k - m] =
              (dp[i][j + cnt[i] - k - m] +
               dp[i - 1][j] * C[cnt[i] - 1][k - 1] % mod * C[j][m] % mod *
                   C[lim - 1 - j + 2][k - m] % mod) %
              mod;
        }
      }
    }
    lim += cnt[i];
  }
  long long ans = dp[sz - 1][0];
  for (int i = 0; i < sz; i++) {
    ans = ans * fact[cnt[i]] % mod;
  }
  printf("%I64d\n", ans);
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d", &a[i]);
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    for (int j = i; j < n; j++) {
      if (check((long long)a[i] * a[j])) {
        cnt[sz]++;
        vis[j] = 1;
      }
    }
    sz++;
  }
  init();
  solve();
}

```