#include <bits/stdc++.h>
using namespace std;
const long long maxn = 350;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
long long n, a, x, b[maxn], f[maxn], fp[maxn], inv[maxn], dp[maxn][maxn], ans,
    dp2[maxn][maxn];
map<long long, long long> c;
long long pw(long long pa, long long push_back) {
  if (push_back == 0) return 1;
  long long pc = pw(pa, push_back / 2);
  pc = (pc * pc) % mod;
  if (push_back & 1) pc = (pc * pa) % mod;
  return pc;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  f[0] = fp[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    f[i] = (f[i - 1] * i) % mod;
    fp[i] = pw(f[i], mod - 2);
    inv[i] = pw(i, mod - 2);
  }
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a;
    x = 1;
    for (long long j = 2; j * j <= a; j++) {
      if (a % j == 0) {
        while (a % (j * j) == 0) a /= j * j;
        if (a % j == 0) a /= j, x *= j;
      }
    }
    x *= a;
    c[x]++;
  }
  x = 1;
  for (map<long long, long long>::iterator it = c.begin(); it != c.end();
       it++) {
    b[x++] = it->second;
  }
  dp2[0][0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= i; j++) {
      for (long long k = 1; k <= i; k++) {
        dp2[i][j] =
            (dp2[i][j] +
             ((((dp2[i - k][j - 1] * k) % mod) * f[i - 1]) % mod) * fp[i - k]) %
            mod;
      }
    }
  }
  dp[0][0] = 1;
  for (long long i = 1; i < x; i++) {
    for (long long j = 0; j <= n; j++) {
      for (long long k = 1; k <= b[i]; k++) {
        if (j < k) continue;
        dp[i][j] = (dp[i][j] + (dp[i - 1][j - k] * dp2[b[i]][k]) % mod) % mod;
      }
    }
  }
  for (long long i = 0; i <= n; i++) {
    if (i % 2 == n % 2)
      ans = (ans + dp[x - 1][i] * f[i]) % mod;
    else
      ans = (ans - dp[x - 1][i] * f[i]) % mod;
  }
  cout << (ans + mod) % mod;
  return 0;
}

### Prompt

Your challenge is to write 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 maxn = 350;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
long long n, a, x, b[maxn], f[maxn], fp[maxn], inv[maxn], dp[maxn][maxn], ans,
    dp2[maxn][maxn];
map<long long, long long> c;
long long pw(long long pa, long long push_back) {
  if (push_back == 0) return 1;
  long long pc = pw(pa, push_back / 2);
  pc = (pc * pc) % mod;
  if (push_back & 1) pc = (pc * pa) % mod;
  return pc;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  f[0] = fp[0] = 1;
  for (long long i = 1; i < maxn; i++) {
    f[i] = (f[i - 1] * i) % mod;
    fp[i] = pw(f[i], mod - 2);
    inv[i] = pw(i, mod - 2);
  }
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a;
    x = 1;
    for (long long j = 2; j * j <= a; j++) {
      if (a % j == 0) {
        while (a % (j * j) == 0) a /= j * j;
        if (a % j == 0) a /= j, x *= j;
      }
    }
    x *= a;
    c[x]++;
  }
  x = 1;
  for (map<long long, long long>::iterator it = c.begin(); it != c.end();
       it++) {
    b[x++] = it->second;
  }
  dp2[0][0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= i; j++) {
      for (long long k = 1; k <= i; k++) {
        dp2[i][j] =
            (dp2[i][j] +
             ((((dp2[i - k][j - 1] * k) % mod) * f[i - 1]) % mod) * fp[i - k]) %
            mod;
      }
    }
  }
  dp[0][0] = 1;
  for (long long i = 1; i < x; i++) {
    for (long long j = 0; j <= n; j++) {
      for (long long k = 1; k <= b[i]; k++) {
        if (j < k) continue;
        dp[i][j] = (dp[i][j] + (dp[i - 1][j - k] * dp2[b[i]][k]) % mod) % mod;
      }
    }
  }
  for (long long i = 0; i <= n; i++) {
    if (i % 2 == n % 2)
      ans = (ans + dp[x - 1][i] * f[i]) % mod;
    else
      ans = (ans - dp[x - 1][i] * f[i]) % mod;
  }
  cout << (ans + mod) % mod;
  return 0;
}

```