#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
using namespace std;
namespace Comb {
int f[320], g[320];
int Power(int x, int y) {
  int o;
  for (o = 1; y; y >>= 1) {
    if (y & 1) o = (long long)o * x % 1000000007;
    x = (long long)x * x % 1000000007;
  }
  return o;
}
void InitComb(void) {
  int i;
  for (i = f[0] = 1; i < 320; i++) f[i] = (long long)f[i - 1] * i % 1000000007;
  g[320 - 1] = Power(f[320 - 1], 1000000007 - 2);
  for (i = 320 - 2; i > -1; i--)
    g[i] = (long long)g[i + 1] * (i + 1) % 1000000007;
  return;
}
int C(int n, int m) {
  return m < 0 || m > n
             ? 0
             : (long long)f[n] * g[m] % 1000000007 * g[n - m] % 1000000007;
}
}  // namespace Comb
int a[320], b[320];
int f[320][320];
inline int Mod(int x) { return x + ((x >> 31) & 1000000007); }
int main(void) {
  int n;
  int i, j, k, s, c;
  Comb::InitComb();
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    for (j = 2, k = a[i], s = 1; j * j <= k; j++) {
      for (c = 0; !(k % j); k /= j, c ^= 1)
        ;
      if (c) s *= j;
    }
    a[i] = s * k;
  }
  sort(a, a + n);
  for (i = c = 0; i < n; i = j) {
    for (j = i; j < n && a[j] == a[i]; j++)
      ;
    b[++c] = j - i;
  }
  f[0][0] = 1;
  for (i = 1; i <= c; i++)
    for (j = 0; j <= n; j++)
      for (k = 0; k < b[i]; k++)
        if (b[i] - k <= j) {
          if (k & 1)
            f[i][j] = Mod(f[i][j] - (long long)f[i - 1][j - (b[i] - k)] *
                                        Comb::C(b[i] - 1, k) % 1000000007 *
                                        Comb::g[b[i] - k] % 1000000007);
          else
            f[i][j] =
                Mod(f[i][j] +
                    (long long)f[i - 1][j - (b[i] - k)] * Comb::C(b[i] - 1, k) %
                        1000000007 * Comb::g[b[i] - k] % 1000000007 -
                    1000000007);
        }
  for (i = s = 0; i <= n; i++)
    s = Mod(s + (long long)Comb::f[i] * f[c][i] % 1000000007 - 1000000007);
  for (i = 1; i <= c; i++) s = (long long)s * Comb::f[b[i]] % 1000000007;
  cout << s << endl;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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>
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
using namespace std;
namespace Comb {
int f[320], g[320];
int Power(int x, int y) {
  int o;
  for (o = 1; y; y >>= 1) {
    if (y & 1) o = (long long)o * x % 1000000007;
    x = (long long)x * x % 1000000007;
  }
  return o;
}
void InitComb(void) {
  int i;
  for (i = f[0] = 1; i < 320; i++) f[i] = (long long)f[i - 1] * i % 1000000007;
  g[320 - 1] = Power(f[320 - 1], 1000000007 - 2);
  for (i = 320 - 2; i > -1; i--)
    g[i] = (long long)g[i + 1] * (i + 1) % 1000000007;
  return;
}
int C(int n, int m) {
  return m < 0 || m > n
             ? 0
             : (long long)f[n] * g[m] % 1000000007 * g[n - m] % 1000000007;
}
}  // namespace Comb
int a[320], b[320];
int f[320][320];
inline int Mod(int x) { return x + ((x >> 31) & 1000000007); }
int main(void) {
  int n;
  int i, j, k, s, c;
  Comb::InitComb();
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    for (j = 2, k = a[i], s = 1; j * j <= k; j++) {
      for (c = 0; !(k % j); k /= j, c ^= 1)
        ;
      if (c) s *= j;
    }
    a[i] = s * k;
  }
  sort(a, a + n);
  for (i = c = 0; i < n; i = j) {
    for (j = i; j < n && a[j] == a[i]; j++)
      ;
    b[++c] = j - i;
  }
  f[0][0] = 1;
  for (i = 1; i <= c; i++)
    for (j = 0; j <= n; j++)
      for (k = 0; k < b[i]; k++)
        if (b[i] - k <= j) {
          if (k & 1)
            f[i][j] = Mod(f[i][j] - (long long)f[i - 1][j - (b[i] - k)] *
                                        Comb::C(b[i] - 1, k) % 1000000007 *
                                        Comb::g[b[i] - k] % 1000000007);
          else
            f[i][j] =
                Mod(f[i][j] +
                    (long long)f[i - 1][j - (b[i] - k)] * Comb::C(b[i] - 1, k) %
                        1000000007 * Comb::g[b[i] - k] % 1000000007 -
                    1000000007);
        }
  for (i = s = 0; i <= n; i++)
    s = Mod(s + (long long)Comb::f[i] * f[c][i] % 1000000007 - 1000000007);
  for (i = 1; i <= c; i++) s = (long long)s * Comb::f[b[i]] % 1000000007;
  cout << s << endl;
  return 0;
}

```