#include <bits/stdc++.h>
using namespace std;
void ReadFile(string f) {
  freopen(((string)f + ".inp").c_str(), "r", stdin);
  freopen(((string)f + ".out").c_str(), "w", stdout);
}
const long long M = 1e9 + 7;
long long n, a[311], dp[311][311], gr[311], m, fact[311], inv_fact[311];
map<long long, long long> mp;
bool check(long long x) {
  long long r = sqrt(x);
  return (r * r == x);
}
long long inv(long long x, long long p = M - 2) {
  if (p == 1) return x;
  long long r = inv(x, p / 2);
  r = (r * r) % M;
  if (p % 2) r = (r * x) % M;
  return r;
}
long long C(long long k, long long n) {
  if (k > n) return 0;
  return (((fact[n] * inv_fact[k]) % M) * inv_fact[n - k]) % M;
}
void local_run() {
  fact[0] = 1;
  for (long long i = 1; i <= 300; ++i) fact[i] = (fact[i - 1] * i) % M;
  inv_fact[300] = inv(fact[300]);
  for (long long i = 299; i >= 0; --i)
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % M;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) {
    if (!a[i]) continue;
    gr[++m]++;
    for (long long j = i + 1; j <= n; j++) {
      if (!a[j]) continue;
      if (check(a[i] * a[j])) {
        a[j] = 0;
        gr[m]++;
      }
    }
    a[i] = 0;
  }
  long long c[311];
  c[0] = 0;
  for (long long i = 1; i <= m; ++i) c[i] = c[i - 1] + gr[i];
  dp[1][gr[1] - 1] = fact[gr[1]];
  for (long long i = 1; i <= m; ++i) {
    for (long long j = 0; j < c[i]; ++j) {
      for (long long k = 1; k <= min(gr[i + 1], c[i] + 1); ++k) {
        for (long long l = 0; l <= min(j, k); ++l) {
          long long w =
              (((fact[gr[i + 1]] * C(k - 1, gr[i + 1] - 1)) % M * C(l, j)) % M *
               C(k - l, c[i] - j + 1)) %
              M;
          dp[i + 1][j - l + gr[i + 1] - k] =
              (dp[i + 1][j - l + gr[i + 1] - k] + w * dp[i][j]) % M;
        }
      }
    }
  }
  cout << dp[m][0];
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  local_run();
}

### 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;
void ReadFile(string f) {
  freopen(((string)f + ".inp").c_str(), "r", stdin);
  freopen(((string)f + ".out").c_str(), "w", stdout);
}
const long long M = 1e9 + 7;
long long n, a[311], dp[311][311], gr[311], m, fact[311], inv_fact[311];
map<long long, long long> mp;
bool check(long long x) {
  long long r = sqrt(x);
  return (r * r == x);
}
long long inv(long long x, long long p = M - 2) {
  if (p == 1) return x;
  long long r = inv(x, p / 2);
  r = (r * r) % M;
  if (p % 2) r = (r * x) % M;
  return r;
}
long long C(long long k, long long n) {
  if (k > n) return 0;
  return (((fact[n] * inv_fact[k]) % M) * inv_fact[n - k]) % M;
}
void local_run() {
  fact[0] = 1;
  for (long long i = 1; i <= 300; ++i) fact[i] = (fact[i - 1] * i) % M;
  inv_fact[300] = inv(fact[300]);
  for (long long i = 299; i >= 0; --i)
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % M;
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) {
    if (!a[i]) continue;
    gr[++m]++;
    for (long long j = i + 1; j <= n; j++) {
      if (!a[j]) continue;
      if (check(a[i] * a[j])) {
        a[j] = 0;
        gr[m]++;
      }
    }
    a[i] = 0;
  }
  long long c[311];
  c[0] = 0;
  for (long long i = 1; i <= m; ++i) c[i] = c[i - 1] + gr[i];
  dp[1][gr[1] - 1] = fact[gr[1]];
  for (long long i = 1; i <= m; ++i) {
    for (long long j = 0; j < c[i]; ++j) {
      for (long long k = 1; k <= min(gr[i + 1], c[i] + 1); ++k) {
        for (long long l = 0; l <= min(j, k); ++l) {
          long long w =
              (((fact[gr[i + 1]] * C(k - 1, gr[i + 1] - 1)) % M * C(l, j)) % M *
               C(k - l, c[i] - j + 1)) %
              M;
          dp[i + 1][j - l + gr[i + 1] - k] =
              (dp[i + 1][j - l + gr[i + 1] - k] + w * dp[i][j]) % M;
        }
      }
    }
  }
  cout << dp[m][0];
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  local_run();
}

```