#include <bits/stdc++.h>
using namespace std;
const int mo = 1000000007;
int n, x, t, P[32005], a[305];
long long f[305], C[305][305], O[305], nO[305];
int main() {
  for (int i = 2; i <= 32000; ++i) {
    if (!P[i]) P[++t] = i;
    for (int j = 1; j <= t; ++j) {
      x = P[j] * i;
      if (x > 32000) break;
      P[x] = 1;
      if (i % P[j] == 0) break;
    }
  }
  for (int i = 1; i <= t; ++i) P[i] *= P[i];
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    for (int j = 1; j <= t && P[j] <= a[i]; ++j)
      while (a[i] % P[j] == 0) a[i] /= P[j];
  }
  O[0] = 1;
  for (int i = 1; i <= n; ++i) O[i] = O[i - 1] * i % mo;
  nO[n] = 1;
  x = O[n];
  for (int k = mo - 2; k; k >>= 1, x = 1ll * x * x % mo)
    if (k & 1) (nO[n] *= x) %= mo;
  for (int i = n - 1; ~i; --i) nO[i] = nO[i + 1] * (i + 1) % mo;
  C[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mo;
  }
  sort(a + 1, a + n + 1);
  f[0] = 1;
  for (int i = 1, j; i <= n; i = j) {
    for (j = i; a[j] == a[i]; ++j)
      ;
    x = j - i;
    for (int k = n - 1; ~k; --k)
      for (int t = 1; t < x && t <= k; ++t)
        (f[k] += f[k - t] * C[x - 1][x - t - 1] % mo * O[x] % mo * nO[x - t]) %=
            mo;
  }
  for (int i = 0; i < n; ++i) f[i] = f[i] * O[n - i] % mo;
  for (int i = n - 1; ~i; --i)
    for (int j = i + 1; j < n; ++j) (f[i] -= f[j] * C[j][i] % mo) %= mo;
  printf("%lld\n", (f[0] + mo) % mo);
  return 0;
}

### Prompt

Generate 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 int mo = 1000000007;
int n, x, t, P[32005], a[305];
long long f[305], C[305][305], O[305], nO[305];
int main() {
  for (int i = 2; i <= 32000; ++i) {
    if (!P[i]) P[++t] = i;
    for (int j = 1; j <= t; ++j) {
      x = P[j] * i;
      if (x > 32000) break;
      P[x] = 1;
      if (i % P[j] == 0) break;
    }
  }
  for (int i = 1; i <= t; ++i) P[i] *= P[i];
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    for (int j = 1; j <= t && P[j] <= a[i]; ++j)
      while (a[i] % P[j] == 0) a[i] /= P[j];
  }
  O[0] = 1;
  for (int i = 1; i <= n; ++i) O[i] = O[i - 1] * i % mo;
  nO[n] = 1;
  x = O[n];
  for (int k = mo - 2; k; k >>= 1, x = 1ll * x * x % mo)
    if (k & 1) (nO[n] *= x) %= mo;
  for (int i = n - 1; ~i; --i) nO[i] = nO[i + 1] * (i + 1) % mo;
  C[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mo;
  }
  sort(a + 1, a + n + 1);
  f[0] = 1;
  for (int i = 1, j; i <= n; i = j) {
    for (j = i; a[j] == a[i]; ++j)
      ;
    x = j - i;
    for (int k = n - 1; ~k; --k)
      for (int t = 1; t < x && t <= k; ++t)
        (f[k] += f[k - t] * C[x - 1][x - t - 1] % mo * O[x] % mo * nO[x - t]) %=
            mo;
  }
  for (int i = 0; i < n; ++i) f[i] = f[i] * O[n - i] % mo;
  for (int i = n - 1; ~i; --i)
    for (int j = i + 1; j < n; ++j) (f[i] -= f[j] * C[j][i] % mo) %= mo;
  printf("%lld\n", (f[0] + mo) % mo);
  return 0;
}

```