#include <bits/stdc++.h>
using namespace std;
long long n, m, a[405], c, r, b, cnt;
long long clean(long long X) {
  for (long long l = 2; 1LL * l * l <= X; ++l) {
    while (X % l == 0 && (X / l) % l == 0) X = X / l / l;
  }
  return X;
}
long long dp[305][305], dp2[305][305], k;
int32_t main() {
  cin >> n;
  for (long long l = 0; l < n; ++l) {
    cin >> a[l];
    a[l] = clean(a[l]);
  }
  dp[0][0] = 1;
  sort(a, a + n);
  for (long long l = 0; l < n; ++l) {
    if (l == 0 || a[l] != a[l - 1]) {
      for (long long l2 = 0; l2 < 302; ++l2) {
        cnt = 0;
        for (long long l3 = 0; l3 < 302; ++l3) {
          cnt += dp[l2][l3];
          cnt %= 1000000007LL;
          dp[l2][l3] = 0;
        }
        dp[l2][0] = cnt;
      }
      r = 0;
    }
    for (long long l2 = 0; l2 < 302; ++l2) {
      for (long long l3 = 0; l3 < 302; ++l3) {
        b = l + 1 - (l2 - r + l3) - l3;
        if (b > 0) dp2[l2][l3 + 2] += 1LL * b * dp[l2][l3] % 1000000007LL;
        if (l2 - 1 >= 0 && l2 - r + l3 > 0)
          dp2[l2 - 1][l3 + 2] +=
              1LL * (l2 - r + l3) * dp[l2][l3] % 1000000007LL;
        dp2[l2 + 1][l3 + 1] += 1LL * l3 * dp[l2][l3] % 1000000007LL;
      }
    }
    r += 2;
    memcpy(dp, dp2, sizeof dp);
    memset(dp2, 0LL, sizeof dp2);
  }
  cnt = 0;
  for (long long l3 = 0; l3 < 302; ++l3) {
    cnt += dp[0][l3];
    cnt %= 1000000007LL;
  }
  cout << cnt;
  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;
long long n, m, a[405], c, r, b, cnt;
long long clean(long long X) {
  for (long long l = 2; 1LL * l * l <= X; ++l) {
    while (X % l == 0 && (X / l) % l == 0) X = X / l / l;
  }
  return X;
}
long long dp[305][305], dp2[305][305], k;
int32_t main() {
  cin >> n;
  for (long long l = 0; l < n; ++l) {
    cin >> a[l];
    a[l] = clean(a[l]);
  }
  dp[0][0] = 1;
  sort(a, a + n);
  for (long long l = 0; l < n; ++l) {
    if (l == 0 || a[l] != a[l - 1]) {
      for (long long l2 = 0; l2 < 302; ++l2) {
        cnt = 0;
        for (long long l3 = 0; l3 < 302; ++l3) {
          cnt += dp[l2][l3];
          cnt %= 1000000007LL;
          dp[l2][l3] = 0;
        }
        dp[l2][0] = cnt;
      }
      r = 0;
    }
    for (long long l2 = 0; l2 < 302; ++l2) {
      for (long long l3 = 0; l3 < 302; ++l3) {
        b = l + 1 - (l2 - r + l3) - l3;
        if (b > 0) dp2[l2][l3 + 2] += 1LL * b * dp[l2][l3] % 1000000007LL;
        if (l2 - 1 >= 0 && l2 - r + l3 > 0)
          dp2[l2 - 1][l3 + 2] +=
              1LL * (l2 - r + l3) * dp[l2][l3] % 1000000007LL;
        dp2[l2 + 1][l3 + 1] += 1LL * l3 * dp[l2][l3] % 1000000007LL;
      }
    }
    r += 2;
    memcpy(dp, dp2, sizeof dp);
    memset(dp2, 0LL, sizeof dp2);
  }
  cnt = 0;
  for (long long l3 = 0; l3 < 302; ++l3) {
    cnt += dp[0][l3];
    cnt %= 1000000007LL;
  }
  cout << cnt;
  return 0;
}

```