Ta xét ~1~ trò chơi như sau
~N~ con thỏ lần lượt đứng ở các vị trí ~1~, ~2~, ..., ~N-1~, ~N~. Cho ~1~ hoán vị ~A~ gồm ~N~ số. Sau ~1~ đơn vị thời gian, tất cả các con thỏ sẽ đồng loạt nhảy. Con thỏ ở vị trí ~i~ sẽ nhảy đến vị trí A[i]. Dễ nhận thấy sau ~1~ khoảng thời gian nào đó sau khi bắt đầu trò chơi, các con thỏ sẽ trở về vị trí ban đầu.
Trò chơi này xưa như Alibaba nên Duy đã nghĩ ra ~1~ vấn đề khác hay hơn rất nhiều: đếm số lượng hoán vị ~A~ thỏa mãn sau đúng ~2~ đơn vị thời gian thì tất cả các con thỏ trở về vị trí ban đầu.
Tuy nhiên, Duy nghĩ mãi mà không nghĩ ra. Các bạn hãy giúp Duy nhé
Input
Gồm một số ~n~ duy nhất~(n \le 500)~
Output
Kết quả của bài toán
Sample Input
2
Sample Output
2
Note
Xét ~n = 2~ và hoán vị ~A~ là ~2 1~
Ban đầu con thỏ ~1~ ở vị trí ~1~, con thỏ ~2~ ở vị trí ~2~
Sau ~1~ đơn vị, con thỏ ~1~ sang vị trí ~A[1]~ là vị trí ~2~
Con thỏ ~2~ sang vị trí ~A[2]~ là vị trí ~1~
Sau ~1~ đơn vị nữa, con thỏ ~1~ đang ở vị trí ~2~ đến vị trí ~A[2]~ là ~1~
Con thỏ ~1~ ở vị trí ~1~ đến vị trí ~A[1]~ là ~2~
~\rightarrow~ trở về vị trí ban đầu
Comments