#include <bits/stdc++.h>
const long long maxn = 307;
const long long mod = 1e9 + 7;
using namespace std;
long long num[maxn], a[maxn];
long long f[maxn][maxn];
long long n, cnt, x, sum;
long long jc[maxn], njc[maxn];
long long power(long long x, long long y) {
  if (y == 1) return x;
  long long c = power(x, y / 2);
  c = (c * c) % mod;
  if (y % 2) c = (c * x) % mod;
  return c;
}
long long C(long long x, long long y) {
  if ((x < 0) || (y < 0) || (y > x)) return 0;
  if ((x == 0) || (y == x)) return 1;
  return jc[x] * njc[y] % mod * njc[x - y] % mod;
}
int main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &x);
    long long flag = 0;
    for (long long j = 1; j <= cnt; j++) {
      long long c = trunc(sqrt(x * a[j]));
      if (c * c == x * a[j]) {
        flag = 1;
        num[j]++;
        break;
      }
    }
    if (!flag) num[++cnt] = 1, a[cnt] = x;
  }
  jc[0] = jc[1] = 1;
  njc[0] = njc[1] = 1;
  for (long long i = 2; i <= n; i++) {
    jc[i] = (long long)(jc[i - 1] * i) % mod;
    njc[i] = power(jc[i], mod - 2);
  }
  f[0][0] = 1;
  for (long long i = 1; i <= cnt; i++) {
    for (long long j = 0; j <= sum; j++) {
      for (long long k = 1; k <= num[i]; k++) {
        for (long long l = 0; l <= j; l++) {
          long long d = j - l + num[i] - k;
          if ((d >= 0) && (d < n)) {
            f[i][d] = (f[i][d] + jc[num[i]] * C(num[i] - 1, k - 1) % mod *
                                     C(j, l) % mod * C(sum + 1 - j, k - l) %
                                     mod * f[i - 1][j] % mod) %
                      mod;
          }
        }
      }
    }
    sum += num[i];
  }
  printf("%I64d\n", f[cnt][0]);
}

### Prompt

Please create a solution in CPP 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 maxn = 307;
const long long mod = 1e9 + 7;
using namespace std;
long long num[maxn], a[maxn];
long long f[maxn][maxn];
long long n, cnt, x, sum;
long long jc[maxn], njc[maxn];
long long power(long long x, long long y) {
  if (y == 1) return x;
  long long c = power(x, y / 2);
  c = (c * c) % mod;
  if (y % 2) c = (c * x) % mod;
  return c;
}
long long C(long long x, long long y) {
  if ((x < 0) || (y < 0) || (y > x)) return 0;
  if ((x == 0) || (y == x)) return 1;
  return jc[x] * njc[y] % mod * njc[x - y] % mod;
}
int main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &x);
    long long flag = 0;
    for (long long j = 1; j <= cnt; j++) {
      long long c = trunc(sqrt(x * a[j]));
      if (c * c == x * a[j]) {
        flag = 1;
        num[j]++;
        break;
      }
    }
    if (!flag) num[++cnt] = 1, a[cnt] = x;
  }
  jc[0] = jc[1] = 1;
  njc[0] = njc[1] = 1;
  for (long long i = 2; i <= n; i++) {
    jc[i] = (long long)(jc[i - 1] * i) % mod;
    njc[i] = power(jc[i], mod - 2);
  }
  f[0][0] = 1;
  for (long long i = 1; i <= cnt; i++) {
    for (long long j = 0; j <= sum; j++) {
      for (long long k = 1; k <= num[i]; k++) {
        for (long long l = 0; l <= j; l++) {
          long long d = j - l + num[i] - k;
          if ((d >= 0) && (d < n)) {
            f[i][d] = (f[i][d] + jc[num[i]] * C(num[i] - 1, k - 1) % mod *
                                     C(j, l) % mod * C(sum + 1 - j, k - l) %
                                     mod * f[i - 1][j] % mod) %
                      mod;
          }
        }
      }
    }
    sum += num[i];
  }
  printf("%I64d\n", f[cnt][0]);
}

```