#include <bits/stdc++.h>
using namespace std;
const int MAXN = 301, MOD = 1e9 + 7;
int n, tmp;
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &tmp);
    for (int j = 2; j * j <= tmp; j++) {
      while (tmp % (j * j) == 0) tmp /= j * j;
    }
    a[i] = tmp;
  }
  sort(a + 1, a + n + 1);
  a[0] = -1;
  dp[0][0][0] = 1;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] != a[i - 1]) {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; j + k <= n; k++) {
          if (j + k != 0)
            dp[i][0][j + k - 1] =
                (dp[i][0][j + k - 1] + (long long)dp[i - 1][j][k] * (j + k)) %
                MOD;
          dp[i][0][j + k] =
              (dp[i][0][j + k] + (long long)dp[i - 1][j][k] * (i - j - k)) %
              MOD;
        }
      }
      cnt = 1;
    } else {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
          if (k != 0)
            dp[i][j][k - 1] =
                (dp[i][j][k - 1] + (long long)dp[i - 1][j][k] * k) % MOD;
          dp[i][j][k] = (dp[i][j][k] +
                         (long long)dp[i - 1][j][k] * (i - 2 * cnt + j - k)) %
                        MOD;
          dp[i][j + 1][k] =
              (dp[i][j + 1][k] + (long long)dp[i - 1][j][k] * j) % MOD;
          dp[i][j + 1][k] = (dp[i][j + 1][k] +
                             (long long)dp[i - 1][j][k] * (cnt * 2 - j * 2)) %
                            MOD;
        }
      }
      cnt++;
    }
  }
  printf("%d\n", dp[n][0][0]);
  return 0;
}

### 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>
using namespace std;
const int MAXN = 301, MOD = 1e9 + 7;
int n, tmp;
int a[MAXN];
int dp[MAXN][MAXN][MAXN];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &tmp);
    for (int j = 2; j * j <= tmp; j++) {
      while (tmp % (j * j) == 0) tmp /= j * j;
    }
    a[i] = tmp;
  }
  sort(a + 1, a + n + 1);
  a[0] = -1;
  dp[0][0][0] = 1;
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] != a[i - 1]) {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; j + k <= n; k++) {
          if (j + k != 0)
            dp[i][0][j + k - 1] =
                (dp[i][0][j + k - 1] + (long long)dp[i - 1][j][k] * (j + k)) %
                MOD;
          dp[i][0][j + k] =
              (dp[i][0][j + k] + (long long)dp[i - 1][j][k] * (i - j - k)) %
              MOD;
        }
      }
      cnt = 1;
    } else {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
          if (k != 0)
            dp[i][j][k - 1] =
                (dp[i][j][k - 1] + (long long)dp[i - 1][j][k] * k) % MOD;
          dp[i][j][k] = (dp[i][j][k] +
                         (long long)dp[i - 1][j][k] * (i - 2 * cnt + j - k)) %
                        MOD;
          dp[i][j + 1][k] =
              (dp[i][j + 1][k] + (long long)dp[i - 1][j][k] * j) % MOD;
          dp[i][j + 1][k] = (dp[i][j + 1][k] +
                             (long long)dp[i - 1][j][k] * (cnt * 2 - j * 2)) %
                            MOD;
        }
      }
      cnt++;
    }
  }
  printf("%d\n", dp[n][0][0]);
  return 0;
}

```