#include <bits/stdc++.h>
const long long MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
long long n, d[301][301], a[301], g[301][301], group[301], gr[301];
long long c[301][301], u[301][301], ptr, fact[301];
bool check(long long a, long long b) {
  long long n = a * b;
  long long l = 0, r = 1e9;
  while (l < r) {
    long long mid = (l + r) / 2;
    if (mid * mid < n)
      l = mid + 1;
    else
      r = mid;
  }
  return (l * l == n);
}
long long qpow(long long a, long long b) {
  long long s = 1;
  while (b) {
    if (b % 2) s = s * a % MOD;
    b /= 2;
    a = a * a % MOD;
  }
  return s;
}
long long C(int n, int k) {
  if (k > n || n < 0 || k < 0) return 0;
  if (k == 0) return 1;
  if (n == k) return 1;
  if (u[n][k]) return c[n][k];
  u[n][k] = 1;
  c[n][k] = C(n - 1, k) + C(n - 1, k - 1);
  while (c[n][k] >= MOD) c[n][k] -= MOD;
  return c[n][k];
}
int main() {
  cin >> n;
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = i * fact[i - 1] % MOD;
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (i != j && check(a[i], a[j])) group[i] = group[j];
    }
    if (!group[i]) group[i] = ++ptr;
    gr[group[i]]++;
  }
  d[1][gr[1] - 1] = fact[gr[1]];
  long long sum = 0;
  for (int i = 2; i <= ptr; i++) {
    sum += gr[i - 1];
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= min(gr[i], sum + 1); k++)
        for (int f = 0; f <= min(k, j); f++)
          if (d[i - 1][j]) {
            long long r = d[i - 1][j];
            r = r * fact[gr[i]] % MOD * C(gr[i] - 1, k - 1) % MOD;
            r = r * C(j, f) % MOD * C(sum + 1 - j, k - f) % MOD;
            d[i][j - f + gr[i] - k] += r;
            if (d[i][j - f + gr[i] - k] >= MOD) d[i][j - f + gr[i] - k] -= MOD;
          }
  }
  cout << d[ptr][0];
}

### Prompt

Your task is to create 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>
const long long MOD = 1e9 + 7, INF = 1e18 + 1;
using namespace std;
long long n, d[301][301], a[301], g[301][301], group[301], gr[301];
long long c[301][301], u[301][301], ptr, fact[301];
bool check(long long a, long long b) {
  long long n = a * b;
  long long l = 0, r = 1e9;
  while (l < r) {
    long long mid = (l + r) / 2;
    if (mid * mid < n)
      l = mid + 1;
    else
      r = mid;
  }
  return (l * l == n);
}
long long qpow(long long a, long long b) {
  long long s = 1;
  while (b) {
    if (b % 2) s = s * a % MOD;
    b /= 2;
    a = a * a % MOD;
  }
  return s;
}
long long C(int n, int k) {
  if (k > n || n < 0 || k < 0) return 0;
  if (k == 0) return 1;
  if (n == k) return 1;
  if (u[n][k]) return c[n][k];
  u[n][k] = 1;
  c[n][k] = C(n - 1, k) + C(n - 1, k - 1);
  while (c[n][k] >= MOD) c[n][k] -= MOD;
  return c[n][k];
}
int main() {
  cin >> n;
  fact[0] = 1;
  for (int i = 1; i <= n; i++) fact[i] = i * fact[i - 1] % MOD;
  for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      if (i != j && check(a[i], a[j])) group[i] = group[j];
    }
    if (!group[i]) group[i] = ++ptr;
    gr[group[i]]++;
  }
  d[1][gr[1] - 1] = fact[gr[1]];
  long long sum = 0;
  for (int i = 2; i <= ptr; i++) {
    sum += gr[i - 1];
    for (int j = 0; j < sum; j++)
      for (int k = 1; k <= min(gr[i], sum + 1); k++)
        for (int f = 0; f <= min(k, j); f++)
          if (d[i - 1][j]) {
            long long r = d[i - 1][j];
            r = r * fact[gr[i]] % MOD * C(gr[i] - 1, k - 1) % MOD;
            r = r * C(j, f) % MOD * C(sum + 1 - j, k - f) % MOD;
            d[i][j - f + gr[i] - k] += r;
            if (d[i][j - f + gr[i] - k] >= MOD) d[i][j - f + gr[i] - k] -= MOD;
          }
  }
  cout << d[ptr][0];
}

```