#include <bits/stdc++.h>
using namespace std;
const int N = 300 + 10, mod = 1e9 + 7;
int fac[N], ifac[N];
int val[N], cnt[N];
int dp[N][N];
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int add(int x, int y) { return (x + y) % mod; }
inline int fpow(int x, int y) {
  int ret = 1;
  for (; y; x = 1ll * x * x % mod, y >>= 1)
    if (y & 1) ret = 1ll * ret * x % mod;
  return ret;
}
inline int C(int n, int m) { return mul(fac[n], mul(ifac[m], ifac[n - m])); }
int main() {
  int n;
  cin >> n;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
  ifac[n] = fpow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &val[i]);
    bool flag = 0;
    for (int j = 1; j < i; ++j) {
      long long s = (long long)val[i] * val[j], t = sqrt(s);
      if (t * t == s) {
        ++cnt[j];
        flag = 1;
        break;
      }
    }
    if (!flag) ++cnt[i];
  }
  int m = 0;
  for (int i = 1; i <= n; ++i)
    if (cnt[i]) cnt[++m] = cnt[i];
  dp[0][0] = 1;
  int s = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= s; ++j)
      if (dp[i - 1][j])
        for (int k = 1; k <= cnt[i]; ++k) {
          dp[i][j + k] =
              add(dp[i][j + k],
                  mul(dp[i - 1][j], mul(C(cnt[i] - 1, k - 1), C(j + k, k))));
        }
    s += cnt[i];
  }
  int ans = 0;
  for (int j = 0; j <= s; ++j)
    if ((s - j) & 1)
      ans = add(ans, -dp[m][j]);
    else
      ans = add(ans, dp[m][j]);
  ans = (ans + mod) % mod;
  for (int i = 1; i <= m; ++i) ans = mul(ans, fac[cnt[i]]);
  printf("%d\n", ans);
  return 0;
}

### Prompt

Your challenge is to write 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;
const int N = 300 + 10, mod = 1e9 + 7;
int fac[N], ifac[N];
int val[N], cnt[N];
int dp[N][N];
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int add(int x, int y) { return (x + y) % mod; }
inline int fpow(int x, int y) {
  int ret = 1;
  for (; y; x = 1ll * x * x % mod, y >>= 1)
    if (y & 1) ret = 1ll * ret * x % mod;
  return ret;
}
inline int C(int n, int m) { return mul(fac[n], mul(ifac[m], ifac[n - m])); }
int main() {
  int n;
  cin >> n;
  fac[0] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
  ifac[n] = fpow(fac[n], mod - 2);
  for (int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &val[i]);
    bool flag = 0;
    for (int j = 1; j < i; ++j) {
      long long s = (long long)val[i] * val[j], t = sqrt(s);
      if (t * t == s) {
        ++cnt[j];
        flag = 1;
        break;
      }
    }
    if (!flag) ++cnt[i];
  }
  int m = 0;
  for (int i = 1; i <= n; ++i)
    if (cnt[i]) cnt[++m] = cnt[i];
  dp[0][0] = 1;
  int s = 0;
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j <= s; ++j)
      if (dp[i - 1][j])
        for (int k = 1; k <= cnt[i]; ++k) {
          dp[i][j + k] =
              add(dp[i][j + k],
                  mul(dp[i - 1][j], mul(C(cnt[i] - 1, k - 1), C(j + k, k))));
        }
    s += cnt[i];
  }
  int ans = 0;
  for (int j = 0; j <= s; ++j)
    if ((s - j) & 1)
      ans = add(ans, -dp[m][j]);
    else
      ans = add(ans, dp[m][j]);
  ans = (ans + mod) % mod;
  for (int i = 1; i <= m; ++i) ans = mul(ans, fac[cnt[i]]);
  printf("%d\n", ans);
  return 0;
}

```