#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mod = 1e9 + 7;
int C[N][N];
int a[N];
int sz[N];
int F[N];
int dp[N][N];
int ptr = 0;
int n;
int solve(int idx, int badPairs, int total) {
  if (idx > ptr) return !badPairs;
  int &ret = dp[idx][badPairs];
  if (~ret) return ret;
  ret = 0;
  for (int i = 1; i <= min(total + 1, sz[idx]); i++) {
    for (int j = 0; j <= min(badPairs, i); j++) {
      int nxt = solve(idx + 1, badPairs + sz[idx] - i - j, total + sz[idx]);
      nxt = nxt * 1ll * F[sz[idx]] % mod;
      nxt = nxt * 1ll * C[sz[idx] - 1][i - 1] % mod;
      nxt = nxt * 1ll * C[badPairs][j] % mod;
      nxt = nxt * 1ll * C[total + 1 - badPairs][i - j] % mod;
      ret = (ret + nxt);
      if (ret >= mod) ret -= mod;
    }
  }
  return ret;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++)
    for (int j = 2; j * j <= a[i]; j++)
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    if (a[i] != a[i - 1])
      sz[++ptr] = 1;
    else
      ++sz[ptr];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
      C[i][j] = ((j == 0 || j == i) ? 1 : C[i - 1][j] + C[i - 1][j - 1]) % mod;
  F[0] = 1;
  for (int i = 1; i <= n; i++) F[i] = F[i - 1] * 1ll * i % mod;
  sort(sz + 1, sz + ptr + 1);
  memset(dp, -1, sizeof dp);
  cout << solve(2, sz[1] - 1, sz[1]) * 1ll * F[sz[1]] % mod << '\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 N = 305;
const int mod = 1e9 + 7;
int C[N][N];
int a[N];
int sz[N];
int F[N];
int dp[N][N];
int ptr = 0;
int n;
int solve(int idx, int badPairs, int total) {
  if (idx > ptr) return !badPairs;
  int &ret = dp[idx][badPairs];
  if (~ret) return ret;
  ret = 0;
  for (int i = 1; i <= min(total + 1, sz[idx]); i++) {
    for (int j = 0; j <= min(badPairs, i); j++) {
      int nxt = solve(idx + 1, badPairs + sz[idx] - i - j, total + sz[idx]);
      nxt = nxt * 1ll * F[sz[idx]] % mod;
      nxt = nxt * 1ll * C[sz[idx] - 1][i - 1] % mod;
      nxt = nxt * 1ll * C[badPairs][j] % mod;
      nxt = nxt * 1ll * C[total + 1 - badPairs][i - j] % mod;
      ret = (ret + nxt);
      if (ret >= mod) ret -= mod;
    }
  }
  return ret;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++)
    for (int j = 2; j * j <= a[i]; j++)
      while (a[i] % (j * j) == 0) a[i] /= (j * j);
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    if (a[i] != a[i - 1])
      sz[++ptr] = 1;
    else
      ++sz[ptr];
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= i; j++)
      C[i][j] = ((j == 0 || j == i) ? 1 : C[i - 1][j] + C[i - 1][j - 1]) % mod;
  F[0] = 1;
  for (int i = 1; i <= n; i++) F[i] = F[i - 1] * 1ll * i % mod;
  sort(sz + 1, sz + ptr + 1);
  memset(dp, -1, sizeof dp);
  cout << solve(2, sz[1] - 1, sz[1]) * 1ll * F[sz[1]] % mod << '\n';
  return 0;
}

```