#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const long long int MOD = 1e9 + 7;
long long int triangulo_pascal[MAXN + 2][MAXN + 2];
long long int factorial[MAXN + 2];
int cant_nums[MAXN + 2];
int sum_cant[MAXN + 2];
long long int dp[MAXN + 2][MAXN + 2];
bool calculado[MAXN + 2][MAXN + 2];
bool es_cuadrado_perfecto(long long int a, long long int b) {
  long long int c = a * b;
  long long int raiz = sqrt(c);
  raiz *= raiz;
  return (raiz == c);
}
void lee_entrada(int &n) {
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> grupo(n, 0);
  int cant_grupos = 0;
  for (int i = 0; i < n; i++) {
    if (grupo[i] == 0) {
      grupo[i] = ++cant_grupos;
      cant_nums[cant_grupos] = 1;
      for (int j = i + 1; j < n; j++) {
        if (es_cuadrado_perfecto(a[i], a[j])) {
          grupo[j] = cant_grupos;
          cant_nums[cant_grupos]++;
        }
      }
    }
  }
  n = cant_grupos;
  for (int i = 1; i <= n; i++) {
    sum_cant[i] = cant_nums[i];
    sum_cant[i] += sum_cant[i - 1];
  }
}
void preprocesa() {
  triangulo_pascal[0][0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    triangulo_pascal[i][0] = 1;
    for (int j = 1; j <= MAXN; j++) {
      triangulo_pascal[i][j] = 0;
      triangulo_pascal[i][j] += triangulo_pascal[i - 1][j];
      triangulo_pascal[i][j] += triangulo_pascal[i - 1][j - 1];
      triangulo_pascal[i][j] %= MOD;
    }
  }
  factorial[0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1];
    factorial[i] *= (long long int)i;
    factorial[i] %= MOD;
  }
}
long long int F(int n, int k) {
  if (n == 1) {
    if (cant_nums[n] - 1 == k) {
      return factorial[cant_nums[n]];
    } else {
      return 0;
    }
  }
  if (!calculado[n][k]) {
    calculado[n][k] = true;
    int tam = cant_nums[n];
    int total = sum_cant[n - 1];
    int limS = min(tam, total + 1), limD;
    dp[n][k] = 0;
    long long int aux;
    for (int S = 1; S <= limS; S++) {
      limD = S;
      limD = min(limD, total + tam - n - k);
      for (int D = 0; D <= limD; D++) {
        int X = k + S + D - tam;
        if (X < 0 || X > total - n + 1) continue;
        aux = F(n - 1, X);
        aux *= triangulo_pascal[tam - 1][S - 1];
        aux %= MOD;
        aux *= triangulo_pascal[X][D];
        aux %= MOD;
        aux *= triangulo_pascal[total + 1 - X][S - D];
        aux %= MOD;
        aux *= factorial[tam];
        aux %= MOD;
        dp[n][k] += aux;
        dp[n][k] %= MOD;
      }
    }
  }
  return dp[n][k];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  lee_entrada(n);
  preprocesa();
  cout << F(n, 0) << "\n";
  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;
const int MAXN = 300;
const long long int MOD = 1e9 + 7;
long long int triangulo_pascal[MAXN + 2][MAXN + 2];
long long int factorial[MAXN + 2];
int cant_nums[MAXN + 2];
int sum_cant[MAXN + 2];
long long int dp[MAXN + 2][MAXN + 2];
bool calculado[MAXN + 2][MAXN + 2];
bool es_cuadrado_perfecto(long long int a, long long int b) {
  long long int c = a * b;
  long long int raiz = sqrt(c);
  raiz *= raiz;
  return (raiz == c);
}
void lee_entrada(int &n) {
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<int> grupo(n, 0);
  int cant_grupos = 0;
  for (int i = 0; i < n; i++) {
    if (grupo[i] == 0) {
      grupo[i] = ++cant_grupos;
      cant_nums[cant_grupos] = 1;
      for (int j = i + 1; j < n; j++) {
        if (es_cuadrado_perfecto(a[i], a[j])) {
          grupo[j] = cant_grupos;
          cant_nums[cant_grupos]++;
        }
      }
    }
  }
  n = cant_grupos;
  for (int i = 1; i <= n; i++) {
    sum_cant[i] = cant_nums[i];
    sum_cant[i] += sum_cant[i - 1];
  }
}
void preprocesa() {
  triangulo_pascal[0][0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    triangulo_pascal[i][0] = 1;
    for (int j = 1; j <= MAXN; j++) {
      triangulo_pascal[i][j] = 0;
      triangulo_pascal[i][j] += triangulo_pascal[i - 1][j];
      triangulo_pascal[i][j] += triangulo_pascal[i - 1][j - 1];
      triangulo_pascal[i][j] %= MOD;
    }
  }
  factorial[0] = 1;
  for (int i = 1; i <= MAXN; i++) {
    factorial[i] = factorial[i - 1];
    factorial[i] *= (long long int)i;
    factorial[i] %= MOD;
  }
}
long long int F(int n, int k) {
  if (n == 1) {
    if (cant_nums[n] - 1 == k) {
      return factorial[cant_nums[n]];
    } else {
      return 0;
    }
  }
  if (!calculado[n][k]) {
    calculado[n][k] = true;
    int tam = cant_nums[n];
    int total = sum_cant[n - 1];
    int limS = min(tam, total + 1), limD;
    dp[n][k] = 0;
    long long int aux;
    for (int S = 1; S <= limS; S++) {
      limD = S;
      limD = min(limD, total + tam - n - k);
      for (int D = 0; D <= limD; D++) {
        int X = k + S + D - tam;
        if (X < 0 || X > total - n + 1) continue;
        aux = F(n - 1, X);
        aux *= triangulo_pascal[tam - 1][S - 1];
        aux %= MOD;
        aux *= triangulo_pascal[X][D];
        aux %= MOD;
        aux *= triangulo_pascal[total + 1 - X][S - D];
        aux %= MOD;
        aux *= factorial[tam];
        aux %= MOD;
        dp[n][k] += aux;
        dp[n][k] %= MOD;
      }
    }
  }
  return dp[n][k];
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  lee_entrada(n);
  preprocesa();
  cout << F(n, 0) << "\n";
  return 0;
}

```