#include <bits/stdc++.h>
using namespace std;
const int maxn = 310;
long long dp[maxn][maxn], N, fact[maxn], infact[maxn];
const long long mod = 1e9 + 7;
long long mod_pow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
unordered_map<long long, long long> tot;
vector<long long> cnt;
long long C(long long m, long long n) {
  return fact[m] * infact[n] % mod * infact[m - n] % mod;
}
int main() {
  fact[0] = infact[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    fact[i] = i * fact[i - 1] % mod;
    infact[i] = infact[i - 1] * mod_pow(i, mod - 2) % mod;
  }
  dp[0][0] = 1;
  scanf("%lld", &N);
  for (int i = 0; i < N; i++) {
    long long x;
    scanf("%lld", &x);
    bool flag = false;
    for (auto p : tot) {
      long long u = p.first;
      long long res = (long long)(sqrt(u * x) + 0.5);
      if (u * x == res * res) {
        flag = true;
        tot[u]++;
        break;
      }
    }
    if (!flag) tot[x]++;
  }
  for (auto p : tot) {
    cnt.push_back(p.second);
  }
  int sz = tot.size();
  dp[0][0] = 1;
  for (int i = 1; i <= sz; i++) {
    for (int k = 1; k <= N; k++) {
      for (int j = 1; j <= min((int)cnt[i - 1], k); j++) {
        dp[i][k] =
            (dp[i][k] + dp[i - 1][k - j] * C(cnt[i - 1] - 1, j - 1LL) % mod *
                            fact[cnt[i - 1]] % mod * infact[j] % mod) %
            mod;
      }
    }
  }
  long long ans = 0;
  for (long long i = N; i >= 0; i--) {
    long long f = ((N - i) & 1) ? -1LL : 1LL;
    ans += f * dp[sz][i] % mod * fact[i] % mod;
    ans = (ans % mod + mod) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Generate a Cpp solution to 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 maxn = 310;
long long dp[maxn][maxn], N, fact[maxn], infact[maxn];
const long long mod = 1e9 + 7;
long long mod_pow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % mod;
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}
unordered_map<long long, long long> tot;
vector<long long> cnt;
long long C(long long m, long long n) {
  return fact[m] * infact[n] % mod * infact[m - n] % mod;
}
int main() {
  fact[0] = infact[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    fact[i] = i * fact[i - 1] % mod;
    infact[i] = infact[i - 1] * mod_pow(i, mod - 2) % mod;
  }
  dp[0][0] = 1;
  scanf("%lld", &N);
  for (int i = 0; i < N; i++) {
    long long x;
    scanf("%lld", &x);
    bool flag = false;
    for (auto p : tot) {
      long long u = p.first;
      long long res = (long long)(sqrt(u * x) + 0.5);
      if (u * x == res * res) {
        flag = true;
        tot[u]++;
        break;
      }
    }
    if (!flag) tot[x]++;
  }
  for (auto p : tot) {
    cnt.push_back(p.second);
  }
  int sz = tot.size();
  dp[0][0] = 1;
  for (int i = 1; i <= sz; i++) {
    for (int k = 1; k <= N; k++) {
      for (int j = 1; j <= min((int)cnt[i - 1], k); j++) {
        dp[i][k] =
            (dp[i][k] + dp[i - 1][k - j] * C(cnt[i - 1] - 1, j - 1LL) % mod *
                            fact[cnt[i - 1]] % mod * infact[j] % mod) %
            mod;
      }
    }
  }
  long long ans = 0;
  for (long long i = N; i >= 0; i--) {
    long long f = ((N - i) & 1) ? -1LL : 1LL;
    ans += f * dp[sz][i] % mod * fact[i] % mod;
    ans = (ans % mod + mod) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}

```