#include <bits/stdc++.h>
const int INF = 0x7f7f7f7f;
using namespace std;
const int MAXN = 310;
const int MOD = 1000000007;
int N, T, fac[MAXN], ifac[MAXN];
map<int, int> M;
int A[MAXN], dp[MAXN][MAXN];
inline int inv(int a) {
  int x = a, p = MOD - 2, ans = 1;
  while (p) {
    if (p & 1) ans = (((long long)(ans) * (long long)(x)) % MOD);
    x = (((long long)(x) * (long long)(x)) % MOD);
    p >>= 1;
  }
  return ans;
}
inline int C(int n, int m) {
  return (
      ((long long)(fac[n]) *
       (long long)((((long long)(ifac[m]) * (long long)(ifac[n - m])) % MOD))) %
      MOD);
}
int main() {
  int i, k, x, y;
  scanf("%d", &N);
  fac[0] = ifac[0] = 1;
  for (i = 1; i <= N; i++)
    fac[i] = (((long long)(fac[i - 1]) * (long long)(i)) % MOD);
  ifac[N] = inv(fac[N]);
  for (i = N - 1; i >= 1; i--)
    ifac[i] = (((long long)(ifac[i + 1]) * (long long)(i + 1)) % MOD);
  for (i = 1; i <= N; i++) {
    scanf("%d", &x);
    y = 1;
    for (k = 2; k * k <= x; k++)
      if (!(x % k)) {
        bool exp = 0;
        while (!(x % k)) x /= k, exp ^= 1;
        if (exp) y *= k;
      }
    if (x) y *= x;
    M[y]++;
  }
  T = 0;
  for (map<int, int>::iterator it = M.begin(); it != M.end(); it++)
    A[++T] = it->second;
  dp[0][0] = 1;
  for (i = 1, y = A[1]; i <= T; i++, y += A[i])
    for (k = 1; k <= y; k++) {
      for (x = 1; x <= min(k, A[i]); x++)
        dp[i][k] =
            (((dp[i][k]) +
              ((((long long)(dp[i - 1][k - x]) *
                 (long long)((((long long)((((long long)(fac[A[i]]) *
                                             (long long)(C(A[i] - 1, x - 1))) %
                                            MOD)) *
                               (long long)(ifac[x])) %
                              MOD))) %
                MOD))) %
             MOD);
    }
  int Ans = 0, Cur;
  for (i = N; i >= 1; i--) {
    Cur = (((long long)(dp[T][i]) * (long long)(fac[i])) % MOD);
    if ((N - i) & 1) Cur = MOD - Cur;
    Ans = (((Ans) + (Cur)) % MOD);
  }
  printf("%d", Ans);
}

### 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>
const int INF = 0x7f7f7f7f;
using namespace std;
const int MAXN = 310;
const int MOD = 1000000007;
int N, T, fac[MAXN], ifac[MAXN];
map<int, int> M;
int A[MAXN], dp[MAXN][MAXN];
inline int inv(int a) {
  int x = a, p = MOD - 2, ans = 1;
  while (p) {
    if (p & 1) ans = (((long long)(ans) * (long long)(x)) % MOD);
    x = (((long long)(x) * (long long)(x)) % MOD);
    p >>= 1;
  }
  return ans;
}
inline int C(int n, int m) {
  return (
      ((long long)(fac[n]) *
       (long long)((((long long)(ifac[m]) * (long long)(ifac[n - m])) % MOD))) %
      MOD);
}
int main() {
  int i, k, x, y;
  scanf("%d", &N);
  fac[0] = ifac[0] = 1;
  for (i = 1; i <= N; i++)
    fac[i] = (((long long)(fac[i - 1]) * (long long)(i)) % MOD);
  ifac[N] = inv(fac[N]);
  for (i = N - 1; i >= 1; i--)
    ifac[i] = (((long long)(ifac[i + 1]) * (long long)(i + 1)) % MOD);
  for (i = 1; i <= N; i++) {
    scanf("%d", &x);
    y = 1;
    for (k = 2; k * k <= x; k++)
      if (!(x % k)) {
        bool exp = 0;
        while (!(x % k)) x /= k, exp ^= 1;
        if (exp) y *= k;
      }
    if (x) y *= x;
    M[y]++;
  }
  T = 0;
  for (map<int, int>::iterator it = M.begin(); it != M.end(); it++)
    A[++T] = it->second;
  dp[0][0] = 1;
  for (i = 1, y = A[1]; i <= T; i++, y += A[i])
    for (k = 1; k <= y; k++) {
      for (x = 1; x <= min(k, A[i]); x++)
        dp[i][k] =
            (((dp[i][k]) +
              ((((long long)(dp[i - 1][k - x]) *
                 (long long)((((long long)((((long long)(fac[A[i]]) *
                                             (long long)(C(A[i] - 1, x - 1))) %
                                            MOD)) *
                               (long long)(ifac[x])) %
                              MOD))) %
                MOD))) %
             MOD);
    }
  int Ans = 0, Cur;
  for (i = N; i >= 1; i--) {
    Cur = (((long long)(dp[T][i]) * (long long)(fac[i])) % MOD);
    if ((N - i) & 1) Cur = MOD - Cur;
    Ans = (((Ans) + (Cur)) % MOD);
  }
  printf("%d", Ans);
}

```