#include <bits/stdc++.h>
using namespace std;
int n, num[310], tot[310], a[310], g[310], cnt(0);
long long c[310][310], f[310][310], q[310];
inline void mod(long long &x) {
  x = (x >= 1000000007) ? x - 1000000007 : ((x < 0) ? x + 1000000007 : x);
}
void pre() {
  for (int i = 1; i <= n; i++)
    if (!g[i]) {
      g[i] = ++cnt;
      num[cnt] = 1;
      for (int j = i + 1; j <= n; j++)
        if (!g[j] && (long long)sqrt((long long)a[i] * a[j]) *
                             (long long)sqrt((long long)a[i] * a[j]) ==
                         (long long)a[i] * a[j])
          g[j] = cnt, num[cnt]++;
    }
  for (int i = 1; i <= cnt; i++) tot[i] = tot[i - 1] + num[i];
  for (int i = 0; i <= n + 1; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j], mod(c[i][j]);
  }
  q[0] = 1;
  for (int i = 1; i <= n + 1; i++) q[i] = (long long)i * q[i - 1] % 1000000007;
}
void solve() {
  f[1][num[1] - 1] = q[num[1]];
  for (int i = 1; i < cnt; i++)
    for (int j = 0; j < tot[i]; j++)
      if (f[i][j]) {
        for (int k = 1; k <= min(tot[i] + 1, num[i + 1]); k++)
          for (int l = 0; l <= min(k, j); l++)
            f[i + 1][j + num[i + 1] - k - l] +=
                f[i][j] * c[j][l] % 1000000007 * c[tot[i] + 1 - j][k - l] %
                1000000007 * c[num[i + 1] - 1][k - 1] % 1000000007 *
                q[num[i + 1]] % 1000000007,
                mod(f[i + 1][j + num[i + 1] - k - l]);
      }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  pre();
  solve();
  printf("%I64d\n", f[cnt][0]);
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
int n, num[310], tot[310], a[310], g[310], cnt(0);
long long c[310][310], f[310][310], q[310];
inline void mod(long long &x) {
  x = (x >= 1000000007) ? x - 1000000007 : ((x < 0) ? x + 1000000007 : x);
}
void pre() {
  for (int i = 1; i <= n; i++)
    if (!g[i]) {
      g[i] = ++cnt;
      num[cnt] = 1;
      for (int j = i + 1; j <= n; j++)
        if (!g[j] && (long long)sqrt((long long)a[i] * a[j]) *
                             (long long)sqrt((long long)a[i] * a[j]) ==
                         (long long)a[i] * a[j])
          g[j] = cnt, num[cnt]++;
    }
  for (int i = 1; i <= cnt; i++) tot[i] = tot[i - 1] + num[i];
  for (int i = 0; i <= n + 1; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++)
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j], mod(c[i][j]);
  }
  q[0] = 1;
  for (int i = 1; i <= n + 1; i++) q[i] = (long long)i * q[i - 1] % 1000000007;
}
void solve() {
  f[1][num[1] - 1] = q[num[1]];
  for (int i = 1; i < cnt; i++)
    for (int j = 0; j < tot[i]; j++)
      if (f[i][j]) {
        for (int k = 1; k <= min(tot[i] + 1, num[i + 1]); k++)
          for (int l = 0; l <= min(k, j); l++)
            f[i + 1][j + num[i + 1] - k - l] +=
                f[i][j] * c[j][l] % 1000000007 * c[tot[i] + 1 - j][k - l] %
                1000000007 * c[num[i + 1] - 1][k - 1] % 1000000007 *
                q[num[i + 1]] % 1000000007,
                mod(f[i + 1][j + num[i + 1] - k - l]);
      }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  pre();
  solve();
  printf("%I64d\n", f[cnt][0]);
  return 0;
}

```