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