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