#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 305;
int a[MAXN], cnt[MAXN], vis[MAXN], C[MAXN][MAXN], fac[MAXN], f[MAXN][MAXN];
vector<int> size;
int n, N, total = 0;
void init() {
  C[0][0] = 1;
  for (int i = 1; i < MAXN; i++) C[i][0] = C[i][i] = 1;
  for (int i = 2; i < MAXN; i++)
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    cnt[i] = 1;
    for (int j = i + 1; j <= n; j++) {
      long long x = sqrt((long long)a[i] * a[j]);
      if (x * x == (long long)a[i] * a[j]) vis[j] = 1, cnt[i]++;
    }
  }
  size.push_back(0);
  for (int i = 1; i <= n; i++)
    if (cnt[i] > 0) size.push_back(cnt[i]);
  N = size.size() - 1;
  init();
  f[1][size[1] - 1] = fac[size[1]];
  for (int i = 1; i < N; i++) {
    total += size[i];
    for (int j = 0; j < total; j++) {
      if (!f[i][j]) continue;
      for (int S = 1; S <= min(size[i + 1], total + 1); S++) {
        for (int D = 0; D <= min(S, j); D++) {
          int &now = f[i + 1][j - D + size[i + 1] - S];
          now = (now + (long long)f[i][j] * fac[size[i + 1]] % MOD *
                           C[size[i + 1] - 1][S - 1] % MOD * C[j][D] % MOD *
                           C[total + 1 - j][S - D]) %
                MOD;
        }
      }
    }
  }
  cout << f[N][0] << endl;
  return 0;
}

### Prompt

Your task is to create 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 int MOD = 1e9 + 7;
const int MAXN = 305;
int a[MAXN], cnt[MAXN], vis[MAXN], C[MAXN][MAXN], fac[MAXN], f[MAXN][MAXN];
vector<int> size;
int n, N, total = 0;
void init() {
  C[0][0] = 1;
  for (int i = 1; i < MAXN; i++) C[i][0] = C[i][i] = 1;
  for (int i = 2; i < MAXN; i++)
    for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  fac[0] = 1;
  for (int i = 1; i < MAXN; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    cnt[i] = 1;
    for (int j = i + 1; j <= n; j++) {
      long long x = sqrt((long long)a[i] * a[j]);
      if (x * x == (long long)a[i] * a[j]) vis[j] = 1, cnt[i]++;
    }
  }
  size.push_back(0);
  for (int i = 1; i <= n; i++)
    if (cnt[i] > 0) size.push_back(cnt[i]);
  N = size.size() - 1;
  init();
  f[1][size[1] - 1] = fac[size[1]];
  for (int i = 1; i < N; i++) {
    total += size[i];
    for (int j = 0; j < total; j++) {
      if (!f[i][j]) continue;
      for (int S = 1; S <= min(size[i + 1], total + 1); S++) {
        for (int D = 0; D <= min(S, j); D++) {
          int &now = f[i + 1][j - D + size[i + 1] - S];
          now = (now + (long long)f[i][j] * fac[size[i + 1]] % MOD *
                           C[size[i + 1] - 1][S - 1] % MOD * C[j][D] % MOD *
                           C[total + 1 - j][S - D]) %
                MOD;
        }
      }
    }
  }
  cout << f[N][0] << endl;
  return 0;
}

```