#include <bits/stdc++.h>
using namespace std;
int n;
int a[307];
bool used[307];
vector<pair<int, int> > divs[307];
vector<int> v;
long long fac[307];
long long inv[307];
long long dp[2][307];
long long fastpow(long long x, long long st) {
  long long ret = 1;
  while (st > 0) {
    if ((st % 2) == 0) {
      x = (x * x) % 1000000007;
      st /= 2;
    } else {
      ret = (ret * x) % 1000000007;
      --st;
    }
  }
  return ret;
}
void input() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    int j = 2;
    while (j * j <= a[i]) {
      int cnt = 0;
      while ((a[i] % j) == 0) {
        ++cnt;
        a[i] /= j;
      }
      if (cnt > 0) {
        divs[i].push_back({j, cnt});
      }
      ++j;
    }
    if (a[i] > 1) {
      divs[i].push_back({a[i], 1});
    }
  }
  fac[0] = 1;
  for (int i = 1; i <= n + 2; ++i) {
    fac[i] = (fac[i - 1] * i) % 1000000007;
  }
  inv[n + 2] = fastpow(fac[n + 2], 1000000007 - 2);
  for (int i = n + 1; i >= 0; --i) {
    inv[i] = (inv[i + 1] * (i + 1)) % 1000000007;
  }
}
bool f(int x, int y) {
  int sz1 = divs[x].size();
  int sz2 = divs[y].size();
  int pos1, pos2;
  pos1 = pos2 = 0;
  while (pos1 < sz1 || pos2 < sz2) {
    if (pos1 == sz1) {
      if (divs[y][pos2++].second % 2 == 1) {
        return false;
      }
    } else if (pos2 == sz2) {
      if (divs[x][pos1++].second % 2 == 1) {
        return false;
      }
    } else {
      if (divs[x][pos1].first < divs[y][pos2].first) {
        if (divs[x][pos1++].second % 2 == 1) {
          return false;
        }
      } else if (divs[x][pos1].first > divs[y][pos2].first) {
        if (divs[y][pos2++].second % 2 == 1) {
          return false;
        }
      } else {
        int aux = divs[x][pos1++].second;
        aux += divs[y][pos2++].second;
        if (aux % 2 == 1) {
          return false;
        }
      }
    }
  }
  return true;
}
long long get_comb(int n, int k) {
  long long ret = fac[n];
  ret = (ret * inv[k]) % 1000000007;
  ret = (ret * inv[n - k]) % 1000000007;
  return ret;
}
void solve() {
  for (int i = 1; i <= n; ++i) {
    if (used[i] == true) {
      continue;
    }
    used[i] = true;
    int cnt = 1;
    for (int j = i + 1; j <= n; ++j) {
      if (f(i, j) == true) {
        ++cnt;
        used[j] = true;
      }
    }
    v.push_back(cnt);
  }
  int sz = v.size();
  int prv = 0;
  int nxt = 1;
  for (int i = 0; i < n; ++i) {
    dp[prv][i] = dp[nxt][i] = 0;
  }
  dp[prv][v[0] - 1] = fac[v[0]];
  int sm = v[0];
  for (int i = 1; i < sz; ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[prv][j] == 0) {
        continue;
      }
      int sr = min(sm + 1, v[i]);
      for (int t = 1; t <= sr; ++t) {
        long long coef = get_comb(v[i] - 1, t - 1);
        coef = (coef * fac[v[i]]) % 1000000007;
        for (int z = 0; z <= min(j, t); ++z) {
          long long aux = get_comb(j, z);
          aux = (aux * get_comb(sm + 1 - j, t - z)) % 1000000007;
          aux = (aux * coef) % 1000000007;
          aux = (aux * dp[prv][j]) % 1000000007;
          dp[nxt][j - z + (v[i] - t)] =
              (dp[nxt][j - z + (v[i] - t)] + aux) % 1000000007;
        }
      }
    }
    sm += v[i];
    for (int j = 0; j < n; ++j) {
      dp[prv][j] = 0;
    }
    prv ^= 1;
    nxt ^= 1;
  }
  cout << dp[prv][0] << "\n";
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  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;
int n;
int a[307];
bool used[307];
vector<pair<int, int> > divs[307];
vector<int> v;
long long fac[307];
long long inv[307];
long long dp[2][307];
long long fastpow(long long x, long long st) {
  long long ret = 1;
  while (st > 0) {
    if ((st % 2) == 0) {
      x = (x * x) % 1000000007;
      st /= 2;
    } else {
      ret = (ret * x) % 1000000007;
      --st;
    }
  }
  return ret;
}
void input() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    int j = 2;
    while (j * j <= a[i]) {
      int cnt = 0;
      while ((a[i] % j) == 0) {
        ++cnt;
        a[i] /= j;
      }
      if (cnt > 0) {
        divs[i].push_back({j, cnt});
      }
      ++j;
    }
    if (a[i] > 1) {
      divs[i].push_back({a[i], 1});
    }
  }
  fac[0] = 1;
  for (int i = 1; i <= n + 2; ++i) {
    fac[i] = (fac[i - 1] * i) % 1000000007;
  }
  inv[n + 2] = fastpow(fac[n + 2], 1000000007 - 2);
  for (int i = n + 1; i >= 0; --i) {
    inv[i] = (inv[i + 1] * (i + 1)) % 1000000007;
  }
}
bool f(int x, int y) {
  int sz1 = divs[x].size();
  int sz2 = divs[y].size();
  int pos1, pos2;
  pos1 = pos2 = 0;
  while (pos1 < sz1 || pos2 < sz2) {
    if (pos1 == sz1) {
      if (divs[y][pos2++].second % 2 == 1) {
        return false;
      }
    } else if (pos2 == sz2) {
      if (divs[x][pos1++].second % 2 == 1) {
        return false;
      }
    } else {
      if (divs[x][pos1].first < divs[y][pos2].first) {
        if (divs[x][pos1++].second % 2 == 1) {
          return false;
        }
      } else if (divs[x][pos1].first > divs[y][pos2].first) {
        if (divs[y][pos2++].second % 2 == 1) {
          return false;
        }
      } else {
        int aux = divs[x][pos1++].second;
        aux += divs[y][pos2++].second;
        if (aux % 2 == 1) {
          return false;
        }
      }
    }
  }
  return true;
}
long long get_comb(int n, int k) {
  long long ret = fac[n];
  ret = (ret * inv[k]) % 1000000007;
  ret = (ret * inv[n - k]) % 1000000007;
  return ret;
}
void solve() {
  for (int i = 1; i <= n; ++i) {
    if (used[i] == true) {
      continue;
    }
    used[i] = true;
    int cnt = 1;
    for (int j = i + 1; j <= n; ++j) {
      if (f(i, j) == true) {
        ++cnt;
        used[j] = true;
      }
    }
    v.push_back(cnt);
  }
  int sz = v.size();
  int prv = 0;
  int nxt = 1;
  for (int i = 0; i < n; ++i) {
    dp[prv][i] = dp[nxt][i] = 0;
  }
  dp[prv][v[0] - 1] = fac[v[0]];
  int sm = v[0];
  for (int i = 1; i < sz; ++i) {
    for (int j = 0; j < n; ++j) {
      if (dp[prv][j] == 0) {
        continue;
      }
      int sr = min(sm + 1, v[i]);
      for (int t = 1; t <= sr; ++t) {
        long long coef = get_comb(v[i] - 1, t - 1);
        coef = (coef * fac[v[i]]) % 1000000007;
        for (int z = 0; z <= min(j, t); ++z) {
          long long aux = get_comb(j, z);
          aux = (aux * get_comb(sm + 1 - j, t - z)) % 1000000007;
          aux = (aux * coef) % 1000000007;
          aux = (aux * dp[prv][j]) % 1000000007;
          dp[nxt][j - z + (v[i] - t)] =
              (dp[nxt][j - z + (v[i] - t)] + aux) % 1000000007;
        }
      }
    }
    sm += v[i];
    for (int j = 0; j < n; ++j) {
      dp[prv][j] = 0;
    }
    prv ^= 1;
    nxt ^= 1;
  }
  cout << dp[prv][0] << "\n";
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve();
  return 0;
}

```