Số vòng hoán vị

Cho mảng đã sắp xếp $[1,2,\dots ,n]$ và hoán vị $p_1,p_2,\dots ,p_n$. Mỗi vòng, tất cả các phần tử dịch chuyển theo hoán vị: phần tử ở vị trí $i$ chuyển sang vị trí $p_i$.

Hỏi sau bao nhiêu vòng thì mảng trở về trạng thái ban đầu lần đầu tiên?

Dữ liệu vào

Dòng đầu chứa số nguyên $n$.

Dòng thứ hai chứa $n$ số nguyên $p_1,p_2,\dots ,p_n$.

Dữ liệu ra

In số vòng cần thiết modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 2·{10}^5$

Ví dụ