#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e9 + 7;
double eps = 1e-6;
int mod = 1e9 + 7;
const int N = 300 + 10;
const double pi = acos(-1.0);
long long a[N], c[N][N], g[N][N], dp[N][N], num[N], m, sum, rep[N];
void M(long long& a) {
  a %= mod;
  if (a < 0) a += mod;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    bool flag = 1;
    for (int j = 1; j <= m; j++) {
      long long v = rep[j] * a[i];
      long long q = sqrt(v);
      if ((long long)q * q == v) {
        num[j]++;
        flag = 0;
        break;
      }
    }
    if (flag) num[++m] = 1, rep[m] = a[i];
  }
  c[0][0] = g[0][0] = 1;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
      M(c[i][j] = (j == 0) ? 1 : c[i - 1][j - 1] + c[i - 1][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
      M(g[i][j] = g[i - 1][j] * ((long long)i - 1 + j) % mod +
                  g[i - 1][j - 1] * j % mod);
  dp[0][0] = 1;
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j <= sum; j++)
      for (int k = 1; k <= num[i]; k++)
        for (int l = 0; l <= j; l++)
          M(dp[i][j - l + num[i] - k] += dp[i - 1][j] * g[num[i]][k] % mod *
                                         c[j][l] % mod * c[sum + 1 - j][k - l] %
                                         mod);
    sum += num[i];
  }
  cout << dp[m][0];
}

### Prompt

Please formulate 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 inf = 1e9 + 7;
double eps = 1e-6;
int mod = 1e9 + 7;
const int N = 300 + 10;
const double pi = acos(-1.0);
long long a[N], c[N][N], g[N][N], dp[N][N], num[N], m, sum, rep[N];
void M(long long& a) {
  a %= mod;
  if (a < 0) a += mod;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    bool flag = 1;
    for (int j = 1; j <= m; j++) {
      long long v = rep[j] * a[i];
      long long q = sqrt(v);
      if ((long long)q * q == v) {
        num[j]++;
        flag = 0;
        break;
      }
    }
    if (flag) num[++m] = 1, rep[m] = a[i];
  }
  c[0][0] = g[0][0] = 1;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
      M(c[i][j] = (j == 0) ? 1 : c[i - 1][j - 1] + c[i - 1][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
      M(g[i][j] = g[i - 1][j] * ((long long)i - 1 + j) % mod +
                  g[i - 1][j - 1] * j % mod);
  dp[0][0] = 1;
  for (int i = 1; i <= m; i++) {
    for (int j = 0; j <= sum; j++)
      for (int k = 1; k <= num[i]; k++)
        for (int l = 0; l <= j; l++)
          M(dp[i][j - l + num[i] - k] += dp[i - 1][j] * g[num[i]][k] % mod *
                                         c[j][l] % mod * c[sum + 1 - j][k - l] %
                                         mod);
    sum += num[i];
  }
  cout << dp[m][0];
}

```