#include <bits/stdc++.h>
using namespace std;
const long long N = 305;
const long long MOD = 1e9 + 7;
long long n, sz[N], tot = 0;
long long jie[N], f[N][N], a[N], p[N], ts[N], c[N][N];
long long chk(long long x) {
  long long m = sqrt(x);
  if (m * m == x) return 1;
  return 0;
}
long long cmp(long long x, long long y) { return x > y; }
void pre() {
  for (long long i = 0; i <= n; i++) {
    c[i][i] = c[i][0] = 1;
    c[i][1] = i;
  }
  for (long long i = 3; i <= n; i++)
    for (long long j = 2; j <= i - 1; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  jie[1] = 1;
  for (long long i = 2; i <= n; i++) jie[i] = jie[i - 1] * i % MOD;
}
int main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) {
    long long flag = 0;
    for (long long grp = 1; grp <= tot; grp++)
      if (chk(p[grp] * a[i])) {
        sz[grp]++;
        flag = 1;
        break;
      }
    if (flag == 0) {
      tot++;
      p[tot] = a[i];
      sz[tot] = 1;
    }
  }
  sort(sz + 1, sz + tot + 1, cmp);
  pre();
  ts[0] = 0;
  for (long long i = 1; i <= tot; i++) ts[i] = ts[i - 1] + sz[i];
  f[0][0] = 1;
  long long m = 0;
  for (long long i = 1; i <= tot; i++) {
    for (long long j = 0; j <= m + 1; j++) {
      if (f[i - 1][j] == 0) continue;
      for (long long k = 0; k < sz[i]; k++) {
        long long temp = f[i - 1][j] * c[sz[i] - 1][k];
        temp %= MOD;
        for (long long p = 0; p <= k + 1; p++) {
          long long temp1 = temp * c[j][p];
          temp1 %= MOD;
          f[i][j + sz[i] - 1 - k - p] +=
              (temp1 * c[m + 1 - j][k + 1 - p]) % MOD;
          f[i][j + sz[i] - 1 - k - p] %= MOD;
        }
      }
    }
    m += sz[i];
  }
  for (long long i = 1; i <= tot; i++)
    f[tot][0] = (f[tot][0] * jie[sz[i]]) % MOD;
  cout << f[tot][0];
  return 0;
}

### Prompt

Please formulate 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 long long N = 305;
const long long MOD = 1e9 + 7;
long long n, sz[N], tot = 0;
long long jie[N], f[N][N], a[N], p[N], ts[N], c[N][N];
long long chk(long long x) {
  long long m = sqrt(x);
  if (m * m == x) return 1;
  return 0;
}
long long cmp(long long x, long long y) { return x > y; }
void pre() {
  for (long long i = 0; i <= n; i++) {
    c[i][i] = c[i][0] = 1;
    c[i][1] = i;
  }
  for (long long i = 3; i <= n; i++)
    for (long long j = 2; j <= i - 1; j++)
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
  jie[1] = 1;
  for (long long i = 2; i <= n; i++) jie[i] = jie[i - 1] * i % MOD;
}
int main() {
  cin >> n;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) {
    long long flag = 0;
    for (long long grp = 1; grp <= tot; grp++)
      if (chk(p[grp] * a[i])) {
        sz[grp]++;
        flag = 1;
        break;
      }
    if (flag == 0) {
      tot++;
      p[tot] = a[i];
      sz[tot] = 1;
    }
  }
  sort(sz + 1, sz + tot + 1, cmp);
  pre();
  ts[0] = 0;
  for (long long i = 1; i <= tot; i++) ts[i] = ts[i - 1] + sz[i];
  f[0][0] = 1;
  long long m = 0;
  for (long long i = 1; i <= tot; i++) {
    for (long long j = 0; j <= m + 1; j++) {
      if (f[i - 1][j] == 0) continue;
      for (long long k = 0; k < sz[i]; k++) {
        long long temp = f[i - 1][j] * c[sz[i] - 1][k];
        temp %= MOD;
        for (long long p = 0; p <= k + 1; p++) {
          long long temp1 = temp * c[j][p];
          temp1 %= MOD;
          f[i][j + sz[i] - 1 - k - p] +=
              (temp1 * c[m + 1 - j][k + 1 - p]) % MOD;
          f[i][j + sz[i] - 1 - k - p] %= MOD;
        }
      }
    }
    m += sz[i];
  }
  for (long long i = 1; i <= tot; i++)
    f[tot][0] = (f[tot][0] * jie[sz[i]]) % MOD;
  cout << f[tot][0];
  return 0;
}

```