#include <bits/stdc++.h>
using namespace std;
const long long md = 1e9 + 7;
const int xn = 3e2 + 10;
const int xm = 5e5;
const int SQ = 320;
const int sq = 1e3 + 10;
const long long inf = 1e18 + 10;
long long power(long long a, long long b) {
  return (!b ? 1
             : (b & 1 ? a * power(a * a % md, b / 2) % md
                      : power(a * a % md, b / 2) % md));
}
long long zarb(long long a, long long b) { return (a * b) % md; }
long long jaam(long long a, long long b) { return (a + b) % md; }
int n;
long long dp[xn][xn][xn], a[xn], cnt = 1;
vector<int> vec, adj[xn];
bool Mark[xn];
void DFS(int v) {
  Mark[v] = true;
  vec.push_back(cnt++);
  for (int i = 0; i < adj[v].size(); i++) {
    int u = adj[v][i];
    if (Mark[u]) continue;
    DFS(u);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      long long sqr = sqrt(a[i] * a[j]);
      if (sqr * sqr == a[i] * a[j]) {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (Mark[i]) continue;
    cnt = 1;
    DFS(i);
  }
  dp[0][0][1] = 1;
  for (long long i = 1; i < n; i++) {
    if (vec[i] == 1) {
      for (long long j = 0; j <= i; j++) {
        for (long long k = 1; k <= vec[i - 1]; k++) {
          if (vec[i - 1] - k - 1 + j >= 0)
            dp[i][j + vec[i - 1] - k - 1][1] =
                jaam(dp[i][j + vec[i - 1] - k - 1][1],
                     zarb(dp[i - 1][j][k], j + vec[i - 1] - k));
          dp[i][j + vec[i - 1] - k][1] =
              jaam(dp[i][j + vec[i - 1] - k][1],
                   zarb(dp[i - 1][j][k], i + 1 - j - vec[i - 1] + k));
        }
      }
      continue;
    }
    for (long long j = 0; j < i; j++) {
      for (long long k = 1; k <= vec[i]; k++) {
        if (k > 1)
          dp[i][j][k] =
              jaam(dp[i][j][k], max(0LL, zarb(dp[i - 1][j + 1][k - 1], j + 1)));
        dp[i][j][k] = jaam(dp[i][j][k],
                           max(0LL, zarb(dp[i - 1][j][k], (vec[i - 1] + k))));
        if (k > 1)
          dp[i][j][k] = jaam(dp[i][j][k],
                             max(0LL, zarb(dp[i - 1][j][k - 1],
                                           i + 1 - (vec[i - 1] + k - 1 + j))));
      }
    }
  }
  cout << dp[n - 1][0][vec[n - 1]] << '\n';
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 md = 1e9 + 7;
const int xn = 3e2 + 10;
const int xm = 5e5;
const int SQ = 320;
const int sq = 1e3 + 10;
const long long inf = 1e18 + 10;
long long power(long long a, long long b) {
  return (!b ? 1
             : (b & 1 ? a * power(a * a % md, b / 2) % md
                      : power(a * a % md, b / 2) % md));
}
long long zarb(long long a, long long b) { return (a * b) % md; }
long long jaam(long long a, long long b) { return (a + b) % md; }
int n;
long long dp[xn][xn][xn], a[xn], cnt = 1;
vector<int> vec, adj[xn];
bool Mark[xn];
void DFS(int v) {
  Mark[v] = true;
  vec.push_back(cnt++);
  for (int i = 0; i < adj[v].size(); i++) {
    int u = adj[v][i];
    if (Mark[u]) continue;
    DFS(u);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
      long long sqr = sqrt(a[i] * a[j]);
      if (sqr * sqr == a[i] * a[j]) {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (Mark[i]) continue;
    cnt = 1;
    DFS(i);
  }
  dp[0][0][1] = 1;
  for (long long i = 1; i < n; i++) {
    if (vec[i] == 1) {
      for (long long j = 0; j <= i; j++) {
        for (long long k = 1; k <= vec[i - 1]; k++) {
          if (vec[i - 1] - k - 1 + j >= 0)
            dp[i][j + vec[i - 1] - k - 1][1] =
                jaam(dp[i][j + vec[i - 1] - k - 1][1],
                     zarb(dp[i - 1][j][k], j + vec[i - 1] - k));
          dp[i][j + vec[i - 1] - k][1] =
              jaam(dp[i][j + vec[i - 1] - k][1],
                   zarb(dp[i - 1][j][k], i + 1 - j - vec[i - 1] + k));
        }
      }
      continue;
    }
    for (long long j = 0; j < i; j++) {
      for (long long k = 1; k <= vec[i]; k++) {
        if (k > 1)
          dp[i][j][k] =
              jaam(dp[i][j][k], max(0LL, zarb(dp[i - 1][j + 1][k - 1], j + 1)));
        dp[i][j][k] = jaam(dp[i][j][k],
                           max(0LL, zarb(dp[i - 1][j][k], (vec[i - 1] + k))));
        if (k > 1)
          dp[i][j][k] = jaam(dp[i][j][k],
                             max(0LL, zarb(dp[i - 1][j][k - 1],
                                           i + 1 - (vec[i - 1] + k - 1 + j))));
      }
    }
  }
  cout << dp[n - 1][0][vec[n - 1]] << '\n';
  return 0;
}

```