C. На скамейке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Год назад на скамейке в общественном парке Леха нашёл массив из n чисел. Леха считает, что перестановка p называется правильной если для всех 1 ≤ i < n выполняется условие, что api·api + 1 не является квадратом целого числа. Леха хочет найти количество правильных перестановок по модулю 109 + 7.

Входные данные

В первой строке содержится единственное число n (1 ≤ n ≤ 300) — количество чисел в массиве.

В следующей строке содержится n чисел a1, a2, ... , an (1 ≤ ai ≤ 109) — найденный массив.

Выходные данные

Выведите одно число — количество правильных перестановок по модулю 109 + 7.

Примеры
Входные данные
3
1 2 4
Выходные данные
2
Входные данные
7
5 2 4 2 4 1 1
Выходные данные
144
Примечание

Разберём 1-й пример:

[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 не являются квадратами целого числа.