#include <bits/stdc++.h>
using namespace std;
long long jc[310], ny[310];
long long ksm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007, b >>= 1;
  }
  return res;
}
long long C(long long n, long long m) {
  return (jc[n] * ny[m] % 1000000007) * ny[n - m] % 1000000007;
}
long long a[310], t4[310], t5[310];
long long v[310], t3[310];
long long dp[310], t2[310], dpn[310];
long long ttmp[310], n, cnt;
map<long long, long long> id;
map<long long, long long> vis;
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  jc[0] = 1;
  for (long long i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % 1000000007;
  ny[n] = ksm(jc[n], 1000000007 - 2);
  for (long long i = n - 1; i >= 0; i--)
    ny[i] = (ny[i + 1] * (i + 1) + 1000000007) % 1000000007;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    for (long long j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) x /= (j * j);
    }
    a[i] = x;
    if (!vis[x]) id[++cnt] = x;
    vis[x]++;
  }
  for (long long i = 1; i <= cnt; i++) v[i] = vis[id[i]];
  sort(v + 1, v + 1 + cnt);
  reverse(v + 1, v + 1 + cnt);
  long long usd = v[1];
  dp[usd - 1] = 1;
  for (long long it = 2; it <= cnt; it++) {
    long long c = v[it];
    memset(dpn, 0, sizeof(dpn));
    for (long long i = 0; i < usd; i++) {
      if (!dp[i]) continue;
      for (long long j = 1; j <= c; j++) {
        for (long long k = 0; k <= min(i, j); k++)
          if (usd - i + 1 >= j - k) {
            dpn[i - k + c - j] =
                (long long)(dpn[i - k + c - j] +
                            dp[i] * C(c - 1, j - 1) % 1000000007 * C(i, k) %
                                1000000007 * C(usd - i + 1, j - k) %
                                1000000007) %
                1000000007;
          }
      }
    }
    usd += c;
    memcpy(dp, dpn, sizeof(dp));
  }
  long long ans = dp[0];
  for (long long i = 1; i <= cnt; ++i)
    for (long long j = 1; j <= v[i]; ++j) ans = ans * j % 1000000007;
  cout << ans << endl;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
long long jc[310], ny[310];
long long ksm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % 1000000007;
    a = a * a % 1000000007, b >>= 1;
  }
  return res;
}
long long C(long long n, long long m) {
  return (jc[n] * ny[m] % 1000000007) * ny[n - m] % 1000000007;
}
long long a[310], t4[310], t5[310];
long long v[310], t3[310];
long long dp[310], t2[310], dpn[310];
long long ttmp[310], n, cnt;
map<long long, long long> id;
map<long long, long long> vis;
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  jc[0] = 1;
  for (long long i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % 1000000007;
  ny[n] = ksm(jc[n], 1000000007 - 2);
  for (long long i = n - 1; i >= 0; i--)
    ny[i] = (ny[i + 1] * (i + 1) + 1000000007) % 1000000007;
  for (long long i = 1; i <= n; i++) {
    long long x;
    cin >> x;
    for (long long j = 2; j * j <= x; j++) {
      while (x % (j * j) == 0) x /= (j * j);
    }
    a[i] = x;
    if (!vis[x]) id[++cnt] = x;
    vis[x]++;
  }
  for (long long i = 1; i <= cnt; i++) v[i] = vis[id[i]];
  sort(v + 1, v + 1 + cnt);
  reverse(v + 1, v + 1 + cnt);
  long long usd = v[1];
  dp[usd - 1] = 1;
  for (long long it = 2; it <= cnt; it++) {
    long long c = v[it];
    memset(dpn, 0, sizeof(dpn));
    for (long long i = 0; i < usd; i++) {
      if (!dp[i]) continue;
      for (long long j = 1; j <= c; j++) {
        for (long long k = 0; k <= min(i, j); k++)
          if (usd - i + 1 >= j - k) {
            dpn[i - k + c - j] =
                (long long)(dpn[i - k + c - j] +
                            dp[i] * C(c - 1, j - 1) % 1000000007 * C(i, k) %
                                1000000007 * C(usd - i + 1, j - k) %
                                1000000007) %
                1000000007;
          }
      }
    }
    usd += c;
    memcpy(dp, dpn, sizeof(dp));
  }
  long long ans = dp[0];
  for (long long i = 1; i <= cnt; ++i)
    for (long long j = 1; j <= v[i]; ++j) ans = ans * j % 1000000007;
  cout << ans << endl;
}

```