Giải bài trực tuyến

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 :D đế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é :D

Input

1 số n duy nhất( n <= 500 )

Output

Kết quả của bài toán

Example

Input

2

Output

2

P/s: có vài bạn thấy đề khó hiểu, mình xin giải thích kĩ

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 đ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 đ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

=> trở về vị trí ban đầu

Quên chưa nói 1 điều, dạo này mình lười nên sinh test random, các bạn chạy trâu ko ăn được điểm đâu :p