#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
int n;
long long a[310];
long long dp[310][310];
long long c[310][310];
long long b[310];
long long spaces[310], group[310];
long long frac[310];
inline bool check(long long x) {
  long long tmp = sqrt(x);
  return tmp * tmp == x;
}
void init() {
  c[0][0] = 1;
  for (int i = 1; i < 310; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  frac[0] = 1;
  for (int i = 1; i < 310; i++) frac[i] = frac[i - 1] * i % mod;
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%I64d", a + i);
  int g = 0;
  for (int i = 0; i < n; i++) {
    if (group[i] == 0) {
      group[i] = ++g;
      b[g]++;
      for (int j = i + 1; j < n; j++) {
        long long tmp = a[i] * a[j];
        if (check(tmp)) {
          group[j] = g;
          b[g]++;
        }
      }
    }
  }
  dp[0][0] = 1;
  spaces[0] = 1;
  for (int G = 1; G <= g; G++) spaces[G] = spaces[G - 1] + b[G];
  for (int G = 1; G <= g; G++) {
    for (int ij = 0; ij <= b[G]; ij++) {
      for (int y = 0; y <= spaces[G - 1]; y++) {
        if (dp[G - 1][y] > 0) {
          for (int j = 0; j <= min(ij, y); j++) {
            int i = ij - j;
            int z = spaces[G - 1] - y;
            dp[G][(y - j) + (b[G] - ij)] +=
                dp[G - 1][y] * c[y][j] % mod * c[z][i] % mod *
                c[b[G] - 1][ij - 1] % mod * frac[b[G]] % mod;
            dp[G][(y - j) + (b[G] - ij)] %= mod;
          }
        }
      }
    }
  }
  printf("%I64d\n", dp[g][0] % mod);
}

### 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 mod = 1e9 + 7;
int n;
long long a[310];
long long dp[310][310];
long long c[310][310];
long long b[310];
long long spaces[310], group[310];
long long frac[310];
inline bool check(long long x) {
  long long tmp = sqrt(x);
  return tmp * tmp == x;
}
void init() {
  c[0][0] = 1;
  for (int i = 1; i < 310; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
  }
  frac[0] = 1;
  for (int i = 1; i < 310; i++) frac[i] = frac[i - 1] * i % mod;
}
int main() {
  init();
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%I64d", a + i);
  int g = 0;
  for (int i = 0; i < n; i++) {
    if (group[i] == 0) {
      group[i] = ++g;
      b[g]++;
      for (int j = i + 1; j < n; j++) {
        long long tmp = a[i] * a[j];
        if (check(tmp)) {
          group[j] = g;
          b[g]++;
        }
      }
    }
  }
  dp[0][0] = 1;
  spaces[0] = 1;
  for (int G = 1; G <= g; G++) spaces[G] = spaces[G - 1] + b[G];
  for (int G = 1; G <= g; G++) {
    for (int ij = 0; ij <= b[G]; ij++) {
      for (int y = 0; y <= spaces[G - 1]; y++) {
        if (dp[G - 1][y] > 0) {
          for (int j = 0; j <= min(ij, y); j++) {
            int i = ij - j;
            int z = spaces[G - 1] - y;
            dp[G][(y - j) + (b[G] - ij)] +=
                dp[G - 1][y] * c[y][j] % mod * c[z][i] % mod *
                c[b[G] - 1][ij - 1] % mod * frac[b[G]] % mod;
            dp[G][(y - j) + (b[G] - ij)] %= mod;
          }
        }
      }
    }
  }
  printf("%I64d\n", dp[g][0] % mod);
}

```