On the Bench

Leha는 일 년 전 공원의 벤치에서 n개의 수로 이루어진 배열을 발견했다. Leha는 모든 1 ≤ i < n에 대해 api·api + 1이 완전제곱수가 아니라는 조건이 성립하면 순열 p가 올바르다고 생각한다. Leha는 올바른 순열의 개수를 109 + 7로 나눈 나머지를 구하려고 한다.

입력 데이터의 첫 줄에는 배열의 길이를 나타내는 하나의 정수 n (1 ≤ n ≤ 300)가 주어진다.

다음 줄에는 Leha가 발견한 배열인 n개의 정수 a1, a2, ... , an (1 ≤ ai ≤ 109)가 주어진다.

올바른 순열의 개수를 109 + 7로 나눈 나머지를 하나의 정수로 출력한다.

첫 번째 예제에서:

$[1, 2, 4]$ — 2와 8은 완전제곱수가 아니므로 올바른 순열이다.

$[1, 4, 2]$ — 4는 2의 제곱이므로 잘못된 순열이다.

$[2, 1, 4]$ — 4는 2의 제곱이므로 잘못된 순열이다.

$[2, 4, 1]$ — 4는 2의 제곱이므로 잘못된 순열이다.

$[4, 1, 2]$ — 4는 2의 제곱이므로 잘못된 순열이다.

$[4, 2, 1]$ — 8과 2는 완전제곱수가 아니므로 올바른 순열이다.