#include <bits/stdc++.h>
using namespace std;
const int N = 305;
const int mod = 1e9 + 7;
int n, fact[N], C[N][N], inv[N], dp[N][N];
map<int, int> mp;
int pow(int tmp, int b) {
  int res = 1;
  for (; b; tmp = 1ll * tmp * tmp % mod, b >>= 1)
    if (b & 1) res = 1ll * res * tmp % mod;
  return res;
}
int main() {
  fact[0] = inv[0] = C[0][0] = 1;
  for (int i = 1; i < N; i++) fact[i] = 1ll * fact[i - 1] * i % mod;
  for (int i = 1; i < N; i++) inv[i] = 1ll * inv[i - 1] * pow(i, mod - 2) % mod;
  for (int i = 1; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j < N; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    for (int p = 2; 1ll * p * p <= x; p++)
      while (x % (p * p) == 0) x /= (p * p);
    mp[x]++;
  }
  map<int, int>::iterator it = mp.begin();
  dp[0][0] = 1;
  int cnt = 0, ans = 0;
  for (int i = 1, num = it->second; it != mp.end();
       it++, i++, num += it->second, cnt++)
    for (int k = i; k <= num; k++)
      for (int j = 1; j <= k && j <= it->second; j++)
        dp[i][k] =
            (dp[i][k] + 1ll * dp[i - 1][k - j] * C[it->second - 1][j - 1] %
                            mod * inv[j] % mod * fact[it->second] % mod) %
            mod;
  for (int k = n, f = 1; k >= 1; k--, f = -f)
    ans = (ans + mod + 1ll * f * dp[cnt][k] % mod * fact[k] % mod) % mod;
  printf("%d\n", ans);
  return 0;
}

### Prompt

Create a solution in Cpp for 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 n, fact[N], C[N][N], inv[N], dp[N][N];
map<int, int> mp;
int pow(int tmp, int b) {
  int res = 1;
  for (; b; tmp = 1ll * tmp * tmp % mod, b >>= 1)
    if (b & 1) res = 1ll * res * tmp % mod;
  return res;
}
int main() {
  fact[0] = inv[0] = C[0][0] = 1;
  for (int i = 1; i < N; i++) fact[i] = 1ll * fact[i - 1] * i % mod;
  for (int i = 1; i < N; i++) inv[i] = 1ll * inv[i - 1] * pow(i, mod - 2) % mod;
  for (int i = 1; i < N; i++) {
    C[i][0] = 1;
    for (int j = 1; j < N; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
  }
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    for (int p = 2; 1ll * p * p <= x; p++)
      while (x % (p * p) == 0) x /= (p * p);
    mp[x]++;
  }
  map<int, int>::iterator it = mp.begin();
  dp[0][0] = 1;
  int cnt = 0, ans = 0;
  for (int i = 1, num = it->second; it != mp.end();
       it++, i++, num += it->second, cnt++)
    for (int k = i; k <= num; k++)
      for (int j = 1; j <= k && j <= it->second; j++)
        dp[i][k] =
            (dp[i][k] + 1ll * dp[i - 1][k - j] * C[it->second - 1][j - 1] %
                            mod * inv[j] % mod * fact[it->second] % mod) %
            mod;
  for (int k = n, f = 1; k >= 1; k--, f = -f)
    ans = (ans + mod + 1ll * f * dp[cnt][k] % mod * fact[k] % mod) % mod;
  printf("%d\n", ans);
  return 0;
}

```