#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 7 + 300;
const int MOD = 7 + 1000000000;
const int Prime_N = 7 + 200000;
bool isP[Prime_N];
vector<int> p;
void getprime() {
  memset(isP, true, sizeof(isP));
  for (int i = (2); i < (Prime_N); i++) {
    if (isP[i]) p.push_back(i);
    for (int j = 0; j < ((int)(p).size()) && i * p[j] < Prime_N; j++) {
      isP[i * p[j]] = false;
      if (i % p[j] == 0) break;
    }
  }
}
void inc(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
int d[MAX_N];
int sam[MAX_N];
int f[MAX_N][MAX_N][MAX_N];
int main() {
  getprime();
  int n;
  cin >> n;
  for (int i = (1); i < (n + 1); i++) {
    int dig;
    scanf("%d", &dig);
    int ret = 1;
    for (int j = (0); j < (((int)(p).size())); j++) {
      if (dig < p[j]) break;
      int tmp = 0;
      for (; dig % p[j] == 0; dig /= p[j]) tmp++;
      if (tmp & 1) ret *= p[j];
    }
    if (dig > 1) ret *= dig;
    d[i] = ret;
  }
  sort(d + 1, d + 1 + n);
  sam[1] = 1;
  for (int i = (2); i < (n + 1); i++)
    sam[i] = sam[i - 1] * (d[i] == d[i - 1]) + 1;
  memset(f, 0, sizeof(f));
  f[0][0][0] = 1;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      for (int k = (0); k < (sam[i] + 1); k++) {
        if (!f[i][j][k]) continue;
        if (d[i + 1] != d[i]) {
          inc(f[i + 1][j + k][0], 1ll * f[i][j][k] * (i + 1 - j - k) % MOD);
          if (j + k - 1 >= 0)
            inc(f[i + 1][j + k - 1][0], 1ll * f[i][j][k] * (j + k) % MOD);
          continue;
        }
        int dk = 2 * sam[i] - k;
        inc(f[i + 1][j][k], 1ll * f[i][j][k] * (i + 1 - j - dk) % MOD);
        inc(f[i + 1][j][k + 1], 1ll * f[i][j][k] * dk % MOD);
        if (j - 1 >= 0) inc(f[i + 1][j - 1][k], 1ll * f[i][j][k] * j % MOD);
      }
    }
  }
  printf("%d", f[n][0][0]);
}

### 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;
const int MAX_N = 7 + 300;
const int MOD = 7 + 1000000000;
const int Prime_N = 7 + 200000;
bool isP[Prime_N];
vector<int> p;
void getprime() {
  memset(isP, true, sizeof(isP));
  for (int i = (2); i < (Prime_N); i++) {
    if (isP[i]) p.push_back(i);
    for (int j = 0; j < ((int)(p).size()) && i * p[j] < Prime_N; j++) {
      isP[i * p[j]] = false;
      if (i % p[j] == 0) break;
    }
  }
}
void inc(int &a, int b) {
  if ((a += b) >= MOD) a -= MOD;
}
int d[MAX_N];
int sam[MAX_N];
int f[MAX_N][MAX_N][MAX_N];
int main() {
  getprime();
  int n;
  cin >> n;
  for (int i = (1); i < (n + 1); i++) {
    int dig;
    scanf("%d", &dig);
    int ret = 1;
    for (int j = (0); j < (((int)(p).size())); j++) {
      if (dig < p[j]) break;
      int tmp = 0;
      for (; dig % p[j] == 0; dig /= p[j]) tmp++;
      if (tmp & 1) ret *= p[j];
    }
    if (dig > 1) ret *= dig;
    d[i] = ret;
  }
  sort(d + 1, d + 1 + n);
  sam[1] = 1;
  for (int i = (2); i < (n + 1); i++)
    sam[i] = sam[i - 1] * (d[i] == d[i - 1]) + 1;
  memset(f, 0, sizeof(f));
  f[0][0][0] = 1;
  for (int i = (0); i < (n); i++) {
    for (int j = (0); j < (n); j++) {
      for (int k = (0); k < (sam[i] + 1); k++) {
        if (!f[i][j][k]) continue;
        if (d[i + 1] != d[i]) {
          inc(f[i + 1][j + k][0], 1ll * f[i][j][k] * (i + 1 - j - k) % MOD);
          if (j + k - 1 >= 0)
            inc(f[i + 1][j + k - 1][0], 1ll * f[i][j][k] * (j + k) % MOD);
          continue;
        }
        int dk = 2 * sam[i] - k;
        inc(f[i + 1][j][k], 1ll * f[i][j][k] * (i + 1 - j - dk) % MOD);
        inc(f[i + 1][j][k + 1], 1ll * f[i][j][k] * dk % MOD);
        if (j - 1 >= 0) inc(f[i + 1][j - 1][k], 1ll * f[i][j][k] * j % MOD);
      }
    }
  }
  printf("%d", f[n][0][0]);
}

```