#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  for (x = c - '0'; (c = getchar()) >= '0' && c <= '9';) x = x * 10 + c - '0';
  return x;
}
map<int, int> mp;
int f[2][300 + 5], C[300 + 5][300 + 5];
int main() {
  int n = read(), x, i, j, k, ls = 0, s = 0, p = 0, q = 1, v = 1;
  for (i = 0; i <= n; ++i)
    for (C[i][0] = j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
  for (; n--; ++mp[x])
    for (x = read(), i = 2; i * i <= x; ++i)
      while (x % (i * i) == 0) x /= i * i;
  for (map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
    ls = s;
    s += i->second;
    p ^= 1;
    q ^= 1;
    memset(f[p], 0, sizeof(f[p]));
    for (int i = 2; i <= s - ls; ++i) v = 1LL * v * i % 1000000007;
    if (!ls) {
      f[p][s - 1] = 1;
      continue;
    }
    for (int i = 0; i < ls; ++i)
      if (f[q][i])
        for (j = 0; j <= i && j <= s - ls; ++j)
          for (k = 0; k <= ls + 1 - i && k <= s - ls - j; ++k)
            f[p][i - j + s - ls - j - k] =
                (f[p][i - j + s - ls - j - k] +
                 1LL * f[q][i] * C[i][j] % 1000000007 * C[ls + 1 - i][k] %
                     1000000007 * C[s - ls - 1][j + k - 1]) %
                1000000007;
  }
  printf("%d", 1LL * f[p][0] * v % 1000000007);
}

### Prompt

Please create a solution in cpp 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;
inline int read() {
  int x;
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  for (x = c - '0'; (c = getchar()) >= '0' && c <= '9';) x = x * 10 + c - '0';
  return x;
}
map<int, int> mp;
int f[2][300 + 5], C[300 + 5][300 + 5];
int main() {
  int n = read(), x, i, j, k, ls = 0, s = 0, p = 0, q = 1, v = 1;
  for (i = 0; i <= n; ++i)
    for (C[i][0] = j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000007;
  for (; n--; ++mp[x])
    for (x = read(), i = 2; i * i <= x; ++i)
      while (x % (i * i) == 0) x /= i * i;
  for (map<int, int>::iterator i = mp.begin(); i != mp.end(); ++i) {
    ls = s;
    s += i->second;
    p ^= 1;
    q ^= 1;
    memset(f[p], 0, sizeof(f[p]));
    for (int i = 2; i <= s - ls; ++i) v = 1LL * v * i % 1000000007;
    if (!ls) {
      f[p][s - 1] = 1;
      continue;
    }
    for (int i = 0; i < ls; ++i)
      if (f[q][i])
        for (j = 0; j <= i && j <= s - ls; ++j)
          for (k = 0; k <= ls + 1 - i && k <= s - ls - j; ++k)
            f[p][i - j + s - ls - j - k] =
                (f[p][i - j + s - ls - j - k] +
                 1LL * f[q][i] * C[i][j] % 1000000007 * C[ls + 1 - i][k] %
                     1000000007 * C[s - ls - 1][j + k - 1]) %
                1000000007;
  }
  printf("%d", 1LL * f[p][0] * v % 1000000007);
}

```