#include <bits/stdc++.h>
using namespace std;
int dp[301][301][301], md = 1e9 + 7, n, fr[300], x[300];
inline void ad(int &x, int y) {
  if ((x += y) >= md) x -= md;
}
inline bool sq(int a, int b) {
  long long s = (long long)a * b;
  int z = sqrt(s) + 0.5;
  return (long long)z * z == s;
}
inline int pw(int x, int p) {
  int an = 1;
  while (p) {
    if (p & 1) an = (long long)an * x % md;
    x = (long long)x * x % md;
    p >>= 1;
  }
  return an;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", x + i);
  for (int i = 0; i < (int)(n); ++i)
    if (fr[i] == 0) {
      fr[i] = 1;
      for (int j = i + 1; j < (int)(n); ++j)
        if (sq(x[i], x[j])) ++fr[i], fr[j] = -1;
    }
  vector<int> s;
  for (int i = 0; i < (int)(n); ++i)
    if (fr[i] != -1) s.push_back(fr[i]);
  dp[0][0][0] = 1;
  int i = 0;
  for (int in = 0; in < (int)(s.size()); ++in) {
    int sm = s[in];
    for (int j = 0; j < (int)(sm); ++j) {
      int ni = i + 1;
      for (int bp = 0; bp < (int)(301); ++bp)
        for (int bc = 0; bc < (int)(301); ++bc)
          if (dp[i][bp][bc]) {
            int nbp, nbc, g = i + 1 - bp - (bc << 1) - (j - bc);
            if (bp && bc + 1 < 301) {
              nbp = bp - 1;
              nbc = bc + 1;
              ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * bp % md);
            }
            nbp = bp;
            nbc = bc;
            ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * (bc + j) % md);
            if (bc + 1 < 301) {
              nbp = bp;
              nbc = bc + 1;
              ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * g % md);
            }
          }
      ++i;
    }
    for (int bp = 0; bp < (int)(301); ++bp)
      for (int bc = 1; bc < (int)(301); ++bc) {
        int ex = sm - bc;
        if (ex >= 0 && ex + bp < 301)
          ad(dp[i][ex + bp][0], dp[i][bp][bc]), dp[i][bp][bc] = 0;
      }
  }
  int an = dp[n][0][0];
  printf("%d\n", an);
}

### 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;
int dp[301][301][301], md = 1e9 + 7, n, fr[300], x[300];
inline void ad(int &x, int y) {
  if ((x += y) >= md) x -= md;
}
inline bool sq(int a, int b) {
  long long s = (long long)a * b;
  int z = sqrt(s) + 0.5;
  return (long long)z * z == s;
}
inline int pw(int x, int p) {
  int an = 1;
  while (p) {
    if (p & 1) an = (long long)an * x % md;
    x = (long long)x * x % md;
    p >>= 1;
  }
  return an;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) scanf("%d", x + i);
  for (int i = 0; i < (int)(n); ++i)
    if (fr[i] == 0) {
      fr[i] = 1;
      for (int j = i + 1; j < (int)(n); ++j)
        if (sq(x[i], x[j])) ++fr[i], fr[j] = -1;
    }
  vector<int> s;
  for (int i = 0; i < (int)(n); ++i)
    if (fr[i] != -1) s.push_back(fr[i]);
  dp[0][0][0] = 1;
  int i = 0;
  for (int in = 0; in < (int)(s.size()); ++in) {
    int sm = s[in];
    for (int j = 0; j < (int)(sm); ++j) {
      int ni = i + 1;
      for (int bp = 0; bp < (int)(301); ++bp)
        for (int bc = 0; bc < (int)(301); ++bc)
          if (dp[i][bp][bc]) {
            int nbp, nbc, g = i + 1 - bp - (bc << 1) - (j - bc);
            if (bp && bc + 1 < 301) {
              nbp = bp - 1;
              nbc = bc + 1;
              ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * bp % md);
            }
            nbp = bp;
            nbc = bc;
            ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * (bc + j) % md);
            if (bc + 1 < 301) {
              nbp = bp;
              nbc = bc + 1;
              ad(dp[ni][nbp][nbc], (long long)dp[i][bp][bc] * g % md);
            }
          }
      ++i;
    }
    for (int bp = 0; bp < (int)(301); ++bp)
      for (int bc = 1; bc < (int)(301); ++bc) {
        int ex = sm - bc;
        if (ex >= 0 && ex + bp < 301)
          ad(dp[i][ex + bp][0], dp[i][bp][bc]), dp[i][bp][bc] = 0;
      }
  }
  int an = dp[n][0][0];
  printf("%d\n", an);
}

```