Trật tự chính phương

Kaito là một học sinh trung học đam mê toán học và thường dành thời gian ở thư viện sau giờ học. Một buổi chiều, trong khi dọn dẹp những chồng sách cũ, cậu tình cờ nhặt được một tờ giấy ghi lại một dãy số nguyên kỳ lạ có độ dài \(n\).

Với sự tò mò của mình, Kaito tin rằng có một cách đặc biệt để sắp xếp lại các số sao cho không có hai số nào đứng cạnh nhau mà tích của chúng lại là một số chính phương. Những cách sắp xếp như vậy, Kaito gọi là những hoán vị hợp lệ.

Hãy giúp Kaito đếm xem có bao nhiêu hoán vị hợp lệ như vậy của dãy số đã cho. Do kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 300)\) --- độ dài của dãy số.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \leq a_i \leq 10^9)\) --- các phần tử trong dãy số mà Kaito tìm thấy.

Output

• In ra một số nguyên --- số lượng hoán vị hợp lệ, lấy theo modulo \(10^9 + 7\).

Example

3
1 2 4

2

7
5 2 4 2 4 1 1

144

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 15 & \(n \le 10\)

2 & 20 & \(a_i \le 10^5\)

3 & 65 & Không có ràng buộc bổ sung

\hline
\endtabular