#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 302, M = 1000000007;
int c[N][N];
int f[N];
void pre() {
  for (int i = 0; i < N; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
  }
  f[0] = 1;
  for (int i = 1; i < N; ++i) f[i] = (f[i - 1] * 1LL * i) % M;
}
int n;
int a[N];
void kar() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
}
void gen() {
  n = 9;
  for (int i = 1; i <= n; ++i) a[i] = rnf() % 10 + 1;
}
bool stg(int x, int y) {
  long long u = x * 1LL * y;
  int s = sqrt(u);
  for (int i = s - 3; i <= s + 3; ++i) {
    if ((i * 1LL * i) == u) return true;
  }
  return false;
}
int p[N];
int first(int x) {
  if (x == p[x]) return x;
  return p[x] = first(p[x]);
}
void kpc(int x, int y) {
  x = first(x);
  y = first(y);
  p[x] = y;
}
int q[N];
int dp[N][N];
int solv() {
  memset(dp, 0, sizeof dp);
  memset(q, 0, sizeof q);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (stg(a[i], a[j])) {
        kpc(i, j);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    q[first(i)]++;
  }
  int qq = 0;
  dp[0][1] = 1;
  for (int i = 0; i < n; ++i) {
    if (q[i + 1] == 0) {
      for (int l = 0; l <= qq + 1; ++l) {
        dp[i + 1][l] = dp[i][l];
      }
      continue;
    }
    for (int l = 0; l <= qq + 1; ++l) {
      if (!dp[i][l]) continue;
      int v = (qq + 1) - l;
      for (int k = 1; k <= q[i + 1]; ++k) {
        for (int ql = 0; ql <= l; ++ql) {
          int qv = k - ql;
          if (ql > l || qv > v || v < 0 || qv < 0) continue;
          int u = dp[i][l];
          u = (u * 1LL * c[q[i + 1] - 1][k - 1]) % M;
          u = (u * 1LL * f[q[i + 1]]) % M;
          u = (u * 1LL * c[l][ql]) % M;
          u = (u * 1LL * c[v][qv]) % M;
          dp[i + 1][l + qv + k] = (dp[i + 1][l + qv + k] + u) % M;
        }
      }
    }
    qq += q[i + 1];
  }
  return dp[n][n + 1];
}
int solv0() {
  for (int i = 1; i <= n; ++i) p[i] = i;
  int ans = 0;
  do {
    bool z = true;
    for (int i = 1; i < n; ++i) {
      if (stg(a[p[i]], a[p[i + 1]])) {
        z = false;
        break;
      }
    }
    ans += z;
  } while (next_permutation(p + 1, p + n + 1));
  return ans;
}
int main() {
  pre();
  kar();
  printf("%d\n", solv());
  return 0;
  int tt;
  tt = 1000;
  while (tt--) {
    gen();
    if (solv() != solv0()) {
      printf("WA\n");
      printf("%d\n", n);
      for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
      printf("\n");
      return 0;
    }
  }
  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;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 302, M = 1000000007;
int c[N][N];
int f[N];
void pre() {
  for (int i = 0; i < N; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
  }
  f[0] = 1;
  for (int i = 1; i < N; ++i) f[i] = (f[i - 1] * 1LL * i) % M;
}
int n;
int a[N];
void kar() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
}
void gen() {
  n = 9;
  for (int i = 1; i <= n; ++i) a[i] = rnf() % 10 + 1;
}
bool stg(int x, int y) {
  long long u = x * 1LL * y;
  int s = sqrt(u);
  for (int i = s - 3; i <= s + 3; ++i) {
    if ((i * 1LL * i) == u) return true;
  }
  return false;
}
int p[N];
int first(int x) {
  if (x == p[x]) return x;
  return p[x] = first(p[x]);
}
void kpc(int x, int y) {
  x = first(x);
  y = first(y);
  p[x] = y;
}
int q[N];
int dp[N][N];
int solv() {
  memset(dp, 0, sizeof dp);
  memset(q, 0, sizeof q);
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (stg(a[i], a[j])) {
        kpc(i, j);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    q[first(i)]++;
  }
  int qq = 0;
  dp[0][1] = 1;
  for (int i = 0; i < n; ++i) {
    if (q[i + 1] == 0) {
      for (int l = 0; l <= qq + 1; ++l) {
        dp[i + 1][l] = dp[i][l];
      }
      continue;
    }
    for (int l = 0; l <= qq + 1; ++l) {
      if (!dp[i][l]) continue;
      int v = (qq + 1) - l;
      for (int k = 1; k <= q[i + 1]; ++k) {
        for (int ql = 0; ql <= l; ++ql) {
          int qv = k - ql;
          if (ql > l || qv > v || v < 0 || qv < 0) continue;
          int u = dp[i][l];
          u = (u * 1LL * c[q[i + 1] - 1][k - 1]) % M;
          u = (u * 1LL * f[q[i + 1]]) % M;
          u = (u * 1LL * c[l][ql]) % M;
          u = (u * 1LL * c[v][qv]) % M;
          dp[i + 1][l + qv + k] = (dp[i + 1][l + qv + k] + u) % M;
        }
      }
    }
    qq += q[i + 1];
  }
  return dp[n][n + 1];
}
int solv0() {
  for (int i = 1; i <= n; ++i) p[i] = i;
  int ans = 0;
  do {
    bool z = true;
    for (int i = 1; i < n; ++i) {
      if (stg(a[p[i]], a[p[i + 1]])) {
        z = false;
        break;
      }
    }
    ans += z;
  } while (next_permutation(p + 1, p + n + 1));
  return ans;
}
int main() {
  pre();
  kar();
  printf("%d\n", solv());
  return 0;
  int tt;
  tt = 1000;
  while (tt--) {
    gen();
    if (solv() != solv0()) {
      printf("WA\n");
      printf("%d\n", n);
      for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
      printf("\n");
      return 0;
    }
  }
  return 0;
}

```